常用查找算法（顺序、二分、插值、分块、斐波那契）
- 顺序查找
- 分块查找
- 二分查找
- 插值查找
- 斐波那契查找
- 总结
顺序查找
基本思想
- 属于线性查找和无序查找，从一端开始顺序扫描，直到找到与目标值value相等的元素。
- 这是最基本的查找方法，也是时间复杂度最高的查找算法。
- 在数据过多时，这种方法并不适用。
代码实现
//第一种:顺序查找
public Type SequenceSearch(Type[] list,Type t)
{
for(Type temp : list)
{
if(temp.equals(t))
return temp;
}
return null;
}
分块查找
基本思想
- 属于顺序查找的改进方法，又叫索引顺序查找。
- 将n个元素分成m块(m<=n)，每个块中元素可以没有顺序，但是m个块之间是有序排列，所以特别适合于节点动态变化的情况。
- 分块查找的速度虽然不如二分查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
- 那么索引表的构成就是每个块中的最大元素。
- 查找方式是先对索引表进行二分或顺序查找，选出目标值应该所在的块，然后在块内进行顺序查找。
二分查找
基本思想
- 属于有序查找算法，也叫折半查找，就是将数组每次选取一半进行查找，怎么选取一半就需要让中间值与目标值value进行比较，因为有序，所以中间值小于目标值则选取后半部分，大于目标值则选取前半部分，依此类推，直到找出与目标值相等的元素，否则返回-1或null。
- 这种方法有效的缩减查找次数和查找范围，适用于数据量比较大的有序表。
- 因为前提是有序表，所以对于插入删除等操作过多的数据集并不适用，因为在排序算法上浪费的时间会比较多。
- 一般的时间复杂度是O(log2n)
代码实现
//第二种：二分查找，这里用int类型数组举例，找到中间元素的索引
//非递归
public int BinarySearch(int[] list,int value)
{
int low = 0,high = list.length-1,mid;
while (low<=high)
{
mid = (low+high)/2;
if(list[mid] == value)//如果是寻找String，就用equal
return mid;
if(list[mid]>value)
high = mid-1;
if(list[mid]<value)
low=mid+1;
}
return -1;
}
//递归
public int BinarySearch(int[] list,int value,int low,int high)
{
int mid = (low+high)/2;
if(list[mid] == value)//如果是寻找String，就用equal
return mid;
if(list[mid]>value)
return BinarySearch(list,value,low,mid-1);
if(list[mid]<value)
return BinarySearch(list,value,mid+1,high);
else
return -1;
}
插值查找
基本思想
- 属于二分查找的改进版，二分查找一直重复一半一半的操作，这种操作比较固定，并不会根据目标值的大小进行自适应分段和选择，而插值查找可以根据目标值value进行自适应。
- 下面是百度词条对插值的解释：插值类似于平常查英文字典的方法，在查一个以字母C开头的英文单词时，决不会用二分查找，从字典的中间一页开始，因为知道它的大概位置是在字典的较前面的部分，因此可以从前面的某处查起。
- 既然是二分查找的改进版，那么就要找关键点进行改进，二分是取1/2的有序表进行查找，那么mid就是关键点，二分中mid=(low+high)/2，可以转化成mid=low+(high-low)/2，所以相当于(high-low)/2中的1/2就是所分的比例，那么可以对mid进行改进，mid=low+low+(value-list[low])/(list[high]-list[low])*(high-low)，(value-list[low])/(list[high]-list[low])就是所分的比例。
- 根据目标值在整个有序表中所处的位置，让mid的变化更靠近目标值value，这样也就间接地减少了比较次数。
- 这种方法适用于关键字分布均匀的有序表。
- 复杂度为O(log2(log2n))
代码实现
//第三种：插值查找，用int类型数组举例
public int InsertSearch(int[] list,int value,int low,int high)
{
int mid = low+(value-list[low])/(list[high]-list[low])*(high-low);
if(list[mid] == value)//如果是寻找String，就用equal
return mid;
if(list[mid]>value)
return InsertSearch(list,value,low,mid-1);
if(list[mid]<value)
return InsertSearch(list,value,mid+1,high);
else
return -1;
}
斐波那契查找
基本思想
- 斐波那契数列与0.618有着奇妙的关联，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，所以可以将黄金比例运用到查找中。
- 百度词条：斐波那契搜索，斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F(n)，将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
- 这个方法比较重要，所以百度词条上讲的很清楚！
代码实现
package Searching;
import java.util.Arrays;
public class Fibonaccialo {
public static void main(String[] args) {
int arr[] = {2,4,9,10,13,15,16,19,34};
System.out.println(FibonacciSearch(arr,34)+1);
}
//创建斐波那契数列
public static int[] Fibonacci(int n) {
int[] FibonacciList = new int[n];
FibonacciList[0] = 0;
FibonacciList[1] = 1;
for (int i = 2; i < n; i++) {
FibonacciList[i] = FibonacciList[i - 1] + FibonacciList[i -2];
}
return FibonacciList;
}
//斐波那契查找，返回的是value在list中的索引值，所以在最后可以加一，为了看出效果，我在上面打印的时候再加一
public static int FibonacciSearch(int[] list,int value)
{
int low = 0;
int high = list.length -1;
int k = 0;//表示斐波那契分割的值
int mid = 0;//存放黄金分割点的值
int f[] = Fibonacci(20);//斐波那契数列
//找k值
while (high>f[k] - 1){
k++;
}
//复制到新的数组
int temp[] = Arrays.copyOf(list,f[k]);
//得到f[k]的值可能会大于a的长度,将新数组的多余的部分用数组中的最后一个数字填充
for (int i = high+1; i <temp.length ; i++) {
temp[i] = list[high];
}
//使用while循环，找到value的位置
while (low<=high){//满足这个条件就可以继续找
mid = low+f[k-1]-1;//找到的黄金分割点
if(value<temp[mid]){
high = mid - 1;
k--;
}else if(value>temp[mid]){
low = mid + 1;
k-=2;
}else{
if(mid<=high){
return mid;
}else {
return high;
}
}
}
return -1;
}
}
总结
- 还剩下两种非常重要的查找算法，就是树表和哈希，这两种我就单独写，ball ball大佬们不要嫌弃！
