查询算法中，最常见的有 7 种，分别是：顺序查询、二分查询、插值查询、斐波那契查询、树表查询、分库查询、哈希查询
顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为O(n)。
从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。
缺点：是当n 很大时，平均查找长度较大，效率低； 优点：是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。
二分查找（Binary Search），是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。 这种查找算法每一次比较都使查找范围缩小一半。
给予一个包含 n个带值元素的数组A
- 1、 令 L为0 ， R为 n-1 ；
- 2、 如果L>R，则搜索以失败告终 ；
- 3、 令 m (中间值元素)为 ⌊(L+R)/2⌋；
- 4、 如果 Am<T，令 L为 m + 1 并回到步骤二 ；
- 5、 如果 Am>T，令 R为 m - 1 并回到步骤二；
时间复杂度：折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn) 空间复杂度：O(1)
//二分查找，递归版本
public class BinarySearch2{
//递归查找
public static int binarysearch(int[] a,int value,int low,int high){
int mid = (low + high)/2;
if(value == a[mid]){
return mid;
}else if(value < a[mid])
return binarysearch(a,value,low,mid - 1);
}else if(value > a[mid])
return binarysearch(a,value,mid + 1,high);
}
return -1;
}
//循环查找
public static int binarysearch(int[] a,int value){
int left=0;
int right=a.length-1;
int middle=0;
while(left<=right) {
middle=(left+right)/2;
if(value == a[middle]){
return middle;
}else if(value < a[middle]) {
left=middle - 1;
}else if(value > a[middle]) {
right=middle + 1;
}
}
return middle;
}
public static void main(String[] args) {
//int[] a = {1,4,2,9,8,6,7,0,3,5}
int[] a = {0,1,2,3,4,5,6,7,8,9};
System.out.println(binarysearch(a,4,0,a.length-1));
}
}插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法，
时间复杂度o(logn)，空间复杂度：O（1）。
插入查找：选择下标 = left + (right - left) * (key - arr[left])/(arr[right] - arr[left])
（1）序列为有序序列
（2）根据公式选取比较值，相等返回下标，不相等则根据公式继续查找，未找到返回-1
public static int insertSearch(int[] array, int key) {
return search(array, key, 0, array.length - 1);
}
private static int search(int[] array, int key, int left, int right) {
while (left <= right) {
if (array[left] == array[right]) {
if (array[left] == key)
return left;
else return -1;
}
int middle = left + (right-left)*(key-array[left])/(array[right]-array[left]);
if (array[middle] == key) {
return middle;
}
if (key < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}斐波那契数列我们都知道{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 }，前后的比值会越来越接近0.618，也就是黄金分割点。
查找条件：
(1)数据必须采用顺序存储结构；
(2)数据必须有序。
public static void main(String[] args) {
int[] array = { 1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68,88 };
System.out.println("result: " + fbSearch(array, 42));
}
public static int fbSearch(int[] array, int value) {
if (array == null || array.length == 0) {
return -1;
} else {
int length = array.length;
int[] fb = makeFbArray(20);// 制造一个长度为20的斐波数列
int k = 0;
while (length > fb[k] - 1) {// 找出数组的长度在斐波数列（减1）中的位置，将决定如何拆分
k++;
}
int[] temp = Arrays.copyOf(array, fb[k] - 1);// 构造一个长度为fb[k] - 1的新数列
//对新构造的数组进行 元素补充
for (int i = length; i < temp.length; i++) {
if (i >= length) {
temp[i] = array[length - 1];
}
}
int low = 0;
int hight = array.length - 1;
while (low <= hight) {
int middle = low + fb[k - 1] - 1;
if (temp[middle] > value) {
hight = middle - 1;
k = k - 1;
} else if (temp[middle] < value) {
low = middle + 1;
k = k - 2;
} else {
if (middle <= hight) {
return middle;// 若相等则说明mid即为查找到的位置
} else {
return hight;// middle的值已经大于hight,进入扩展数组的填充部分,即最后一个数就是要查找的数。
}
}
}
return -1;
}
}
private static int[] makeFbArray(int length) {
int[] array = null;
if (length > 2) {
array = new int[length];
array[0] = 1;
array[1] = 1;
for (int i = 2; i < length; i++) {
array[i] = array[i - 1] + array[i - 2];
}
}
return array;
}（------------正在整理中------------）
（------------正在整理中------------）
（------------正在整理中------------）