1 顺序查找
挨个从下标0 - N挨个遍历，找出结果，没什么好说的.直接上代码.
/**
* 顺序查找. 时间复杂度为 O(n)
* @param values
*/
public static final int findByOrder(int []arrays,int value) {
for(int i = 0 ; i < arrays.length; i++) {
if(arrays[i] == value) {
return i;
}
}
System.out.println("顺序查找结束，但并未找到相关数据");
return -1;
}
2 二分法查找
最终的目标是希望a[mid] = value,mid = (lowIndex + hightIndex) / 2, 如果value > a[mid] 显然 在中间下标的右侧，那么 lowIndex = mid + 1;在左侧那么hightIndex = mid - 1;+1，-1是因为没找到的情况下，mid并不是目标。
/**
* 二分法查找.log2(n+1)
* @param arrays
* @param value
*/
public static int findBySecondBinary(int arrays[],int value) {
int lowIndex = 0;
int highIndex = arrays.length - 1;
int length = arrays.length;
while(lowIndex <= highIndex) {
int mid = (lowIndex + highIndex) / 2;
if(arrays[mid] == value) {
return mid;
}
if(arrays[mid] > value) {
highIndex = mid - 1;
}else {
lowIndex = mid + 1;
}
}
//System.out.println("二分法查找结束，但并未找到相关数据");
return -1;
}
3 插值查找
插值查找说白了，差值法查找，也是二分法的升级版. 适合分布比较较均匀的数组.
public static int findByChaZhi(int a[],int value,int low ,int hight) {
if(low > hight) {
return -1;
}
int mid = low + (value - a[low]) / (a[hight] - a[low]) * (hight - low);
if(a[mid] == value) {
return mid;
}
if(value > a[mid]) {
return findByChaZhi(a, value, mid + 1, hight);
}
if(value < a[mid]) {
return findByChaZhi(a, value, low, mid - 1);
}
return -1;
}
4 斐波拉契查找
斐波拉契，从第三个数开始每个数的值都等于前面两个数之和，数学公式f(k) = f(k - 1) + f(k-2) k >= 2, 其算法原理跟二分法都差不多，时间复杂度为logn, 最终都是要a[mid] = value,只是这次mid改为符合斐波拉契数列的方式计算 mid = low + f(k - 1) - 1; 斐波拉契将整个数组分成两段左边的长度用f(k - 1)表示，右边f(k - 2)，那么中间点应该是f(k - 1)位置，f(k - 1) - 1 是因为斐波拉契数列从1开始 而我们的数组下标从0开始.
//这个函数构建斐波拉契数列.
public static int[] getFeiboNaqiArrays(int nums) {
int f[] = new int[nums];
f[0] = 1;
f[1] = 1;
for(int i = 2; i < nums ;i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
/**
* 斐波那契查找，黄金查找法则.斐波那契数列 f(k) = f(k-1) + f(k-2) k >=2;0.618;
* 时间复杂度Log2(n)
* @param data
* @param value.
* @return
*/
public static int findByFeiboNaqi(int data[],int value) {
int low = 0;
int hight = data.length - 1;
int k = 0; //K表示斐波那契数组的索引.
int f[] = getFeiboNaqiArrays(20);
while(f[k] - 1 <= data.length) {
k++;
}
//请注意，这里很关键，得到一个斐波拉契长度大小的数组，超出data.length部分的元素，用data数组的最后一个补全.
int temp[] = new int[f[k]];
for(int i= 0 ; i < f[k] ; i++) {
if(i < data.length) {
temp[i] = data[i];
}else {
temp[i] = data[hight - 1];
}
}
while(low <= hight) {
int midIndex = low + f[k - 1] - 1;
if(temp[midIndex] == value) {
if(midIndex <= hight) {
return midIndex;
}else {
return hight;
}
}
if(temp[midIndex] > value) { //在左边
//k--;
hight = midIndex - 1;
k-=1;
}
if(temp[midIndex] < value) {
low = midIndex + 1;
/*说明值在右边. 因为初始状态是f(k - 1)为左边，右边是f(k -2),
那么右半段斐波拉契数组个数为 f(k - 3) + f(k - 4) ,分割点是
f(k - 3),下一次的mid = midIndex + 1 + f(k - 3) - 1;*/
k-=2;
}
}
return -1;
}
