四种查找算法
1、线性查找算法
1.1、实现的思路：
通过将要查找的值与数组内的每一个元素一个一个的进行比较，若有相同的值，则将该元素的下标填充到 temp数组之中最后返回 temp数组中的元素（即代表了查找到的元素的下标）若是 temp中的元素长度为 0时，返回 -1，若是有多个符合查找条件的值，则将他们每一个的下标都保存至一个数组之中
public static int[] orderSearch(int[] array, int value) {
int[] temp = new int[array.length];
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == value) {
temp[count++] = i;
}
}
if (count == 0) {
temp[0] = -1;
return temp;
} else {
return temp;
}
}
1.2、小结：
1、每当找到一个符合查找条件的值时，将他的下标传入数组之中时，记得将指向该数组当前索引的变量后移一位，不然的话会覆盖前一个
2、若是该数组之中没有符合该条件的元素，则将-1传入到数组之中
2、二分查找算法
2.1、实现的思路：
1、首先确定该数组中间的下标
2、然后将 array[middle]与 value的值进行比较
3、若 array[middle]大于 value，则表示要查找的值在 middle的左边，因此需要递归的向左查找
4、若 array[middle]小于 value，则表示要查找的值在 middle的右边，因此需要递归的向右查找
5、若 array[middle]等于 value，则表示已经找到了需要的值，将其填充到 temp数组之中
6、当找到了符合条件的值的时候，继续向左与向右一个进行比较，看看是否还要符合条件的值，若有，则也将其返回下标且继续向左或者向右查找，直至没有符合条件的值
7、当递归完整个数组都没有找到符合条件的元素时，就需要结束递归，返回 -1（就是当 left > right时）
public static int[] binarySearch(int[] array, int left, int right, int value) {
int middle = (left + right) / 2;
int[] temp = new int[array.length];
int count = 0;
//则表示要查找的值在middle的左边，因此需要递归的向左查找
if (array[middle] > value) {
binarySearch(array, left, middle - 1, value);
}
//则表示要查找的值在middle的右边，因此需要递归的向右查找
if (array[middle] < value) {
binarySearch(array, middle + 1, right, value);
}
//则表示已经找到了需要的值，将其填充到temp数组之中
if (array[middle] == value) {
temp[count++] = middle;
//当找到了符合条件的值的时候，继续向左与向右一个进行比较，看看是否还要符合条件的值，若有，则也将其返回下标
int num1 = middle;
int num2 = middle;
while (true) {
if (array[--num1] == value) {
temp[count++] = num1;
} else {
break;
}
}
while (true) {
if (array[++num2] == value) {
temp[count++] = num2;
} else {
break;
}
}
}
return temp;
}
2.2、小结：
1、二分查找需要数组有序
2、递归的时候要注意结束递归的条件
3、插值查找算法
3.1、实现的思路：
将数组的第 left + (right - left) * (value - array[left]) / (array[right] - array[left])个值与 value进行比较，只需要一次就可以查找该数组是否有与 value相等的值
/**
* 插值查找算法的实现方法
*
* @param array 需要进行查找的数组
* @param left 要查找的最左边的下标
* @param right 要查找的最右边的下标
* @param value 要查找的值
* @return 返回被查找的元素的下标，有多个则返回多个，没有则返回-1
*/
public static int[] insertSearch(int[] array, int left, int right, int value) {
int middle = left + (right - left) * (value - array[left]) / (array[right] - array[left]);
int[] temp = new int[array.length];
int count = 0;
//我们得到的middle是有可能会越界的，所以要进行限制
if (left > right || value < array[0] || value > array[array.length - 1]) {
temp[0] = -1;
return temp;
}
//则表示要查找的值在middle的左边，因此需要递归的向左查找
if (array[middle] > value) {
insertSearch(array, left, middle - 1, value);
}
//则表示要查找的值在middle的右边，因此需要递归的向右查找
if (array[middle] < value) {
insertSearch(array, middle + 1, right, value);
}
//则表示已经找到了需要的值，将其填充到temp数组之中
if (array[middle] == value) {
temp[count++] = middle;
//当找到了符合条件的值的时候，继续向左与向右一个进行比较，看看是否还要符合条件的值，若有，则也将其返回下标
int num1 = middle;
int num2 = middle;
while (true) {
if (array[--num1] == value) {
temp[count++] = num1;
} else {
break;
}
}
while (true) {
if (array[++num2] == value) {
temp[count++] = num2;
} else {
break;
}
}
}
return temp;
}
3.2、小结：
1、其实本质上就是二分查找的一个优化
因为二分插找的算法基础是：
每一次都将数组的中间的那个数与要查找的值进行比较，然后根据两个数的大小关系来确定下一次查找的范围
但是这样查找的缺点是：如果要查找的数在数组的第一个或者最后一个，那么需要比较很多次才能够找到，浪费时间
而插值查找的算法基础是：
将数组的第 left + (right - left) * (value - array[left]) / (array[right] - array[left])个值与value进行比较，
只需要一次就可以查找该数组是否有与 value相等的值
2、注意：插值查找算法也要求数组是有序的
4、斐波那契查找算法
4.1、实现的思路：
将数组的第 left + F(k-1) - 1个值与value进行比较
注意：F(k-1) - 1的理解：
F表示这个斐波那契数列
k表示这个斐波那契数列里面的第几个元素
由于斐波那契数列的特征，可以得到 F(k) = F(k-1) + F(k-2)，以此可以推导得到 F(k) - 1 = (F(k-1)-1) + (F(k-2)-1) + 1
这个式子说明：只要有序数组的长度为 F(k) - 1，就可以将这个数组分为 F(k-1) - 1与 F(k-2) - 1两个数段，即可以得出 middle = left + F(k-1) - 1
类似的斐波那契的每一份子段也可以用这个方法进行分割
但是顺序表的长度不一定为 F(k)-1，所以就需要将原来的数组长度给扩充为 F(k)-1（这里的 k只要能满足 F(k)-1 >= array.length即可
public static int[] fibonacci() {
//首先需要获得一个斐波那契数列
int[] fibonacci = new int[20];
fibonacci[0] = 1;
fibonacci[1] = 1;
for (int i = 2; i < fibonacci.length; i++) {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}
return fibonacci;
}
public static int fibonacciSearch(int[] array, int value) {
int left = 0;
int right = array.length - 1;
//表示斐波那契数列分割数值的下标
int k = 0;
int middle = 0;
//获取到斐波那契数列
int[] fibonacci = fibonacci();
//获取到斐波那契数列分割数值的下标
while (right > fibonacci[k] - 1) {
k++;
}
//因为新得到的斐波那契数列的长度可能会大于原来斐波那契数列的长度，所以要新建一个数组来进行存放，并且指向array[]
int[] temp = Arrays.copyOf(array, fibonacci[k]);
//但是我们要求填充的数是array[]数组的最后一个数
for (int i = right + 1; i < temp.length; i++) {
temp[i] = array[right];
}
while (left <= right) {
middle = left + fibonacci[k - 1] - 1;
//向数组的左边继续寻找
if (value < temp[middle]) {
right = middle - 1;
/*
为什么是 k--
因为：
1、全部元素 = 前面的元素 + 后面的元素
2、fibonacci[k] = fibonacci[k-1] + fibonacci[k-2]
因为前面有fibonacci[k-1]个元素，所以可以继续拆分为fibonacci[k-1] = fibonacci[k-2] + fibonacci[k-3]
即在fibonacci[k-1]的前面继续查找 k--
即下次循环middle = fibonacci[k-1-1]-1
*/
k--;
//在数组的右边继续寻找
} else if (value > temp[middle]) {
left = middle + 1;
/*
为什么是 k -= 2
因为：
1、全部元素 = 前面的元素 + 后面的元素
2、fibonacci[k] = fibonacci[k-1] + fibonacci[k-2]
因为后面有fibonacci[k-2]个元素，所以可以继续拆分为fibonacci[k-1] = fibonacci[k-3] + fibonacci[k-4]
即在fibonacci[k-2]的前面继续查找 k -= 2
即下次循环middle = fibonacci[k-1-2] - 1
*/
k -= 2;
//找到了
} else {
//需要确定，返回的是哪一个下标
if (middle <= right) {
return middle;
} else {
return right;
}
}
}
return -1;
}
4.2、小结：
1、整个斐波那契查找算法的流程就是：
1.1、先根据自己创建的斐波那契数列来得到 k
1.2、因为传入的 array数组不一定可以满足斐波那契查找算法的长度，所以要新建一个数组
1.3、这个新建数组的内容是传入的 array数组的全部元素加上 array数组的最后一个元素填充剩余的空着的地方
1.4、然后在这个新数组里面得到 middle的值
1.5、最后根据这个值来判断是否找到了满足条件的元素
2、其实本质上还是二分查找算法的一个优化
3、因为斐波那契数列越往后，相邻两个数的比值越来越接近与黄金分割点，我们就是根据这个才创建出这么一个查找的算法