死磕数据结构与算法——查找算法。才疏学浅，如有错误，及时指正
- 1. 线性查找算法
-
- 思路：
- 代码
- 2. 二分查找算法
-
- 前提：数组是一个有序的数组。
- 思路：
- 代码：
- 注意：上面只能找到数组的一个下标，
- 3. 插值查找算法
-
- 插值查找的原理：
- 代码：
- 4. 斐波那契查找算法（黄金分割法）
-
- 思路：
- 代码：
- 总结
1. 线性查找算法
思路：
对数组从左到右进行遍历，依次把数组的值与要查找的值进行对比，如果相等，就返回此时的数组下标。如果数组遍历完成之后，依然找不到该值，说明这个数组中没有此值，此时返回-1。
线性查找是最简单的查找算法，但是查找的次数很多。
代码
package Search;
public class SeqSearch {
public static void main(String[] args) {
int arr[] = { 0, 29, 85, 66, 185, 18, 99};
int res = seqSearch( arr, 10000 );
if(res == -1){
System.out.println("没有找到该数据");
}
else{
System.out.println(res);
}
}
public static int seqSearch(int arr[], int value){
for (int i = 0; i < arr.length; i++) {
if(arr[i] == value){
return i;
}
}
return -1;
}
}
2. 二分查找算法
前提：数组是一个有序的数组。
思路：
代码：
package Search;
public class BinerySearch {
public static void main(String[] args) {
int arr[] = { 5, 20, 35, 88, 99, 180 };
int res = binerySearch( arr, 0, arr.length - 1, 88 );
System.out.println(res);
}
public static int binerySearch(int arr[], int left, int right, int value){
int mid = (left + right) / 2;
if(left > right){
return -1;
}else {
if(arr[mid] > value){
//向左进行递归
return binerySearch( arr, left, mid-1, value );
}
else if (arr[mid] < value){
//向右进行递归
return binerySearch( arr, mid+1, right, value );
}
else {
//说明找到了
return mid;
}
}
}
}
注意：上面只能找到数组的一个下标，
下面的是怎么找到所有下标的代码：
public static ArrayList<Integer> binerySearch2(int arr[], int left, int right, int value){
//定义一个集合
ArrayList<Integer> list = new ArrayList<>( );
int mid = (left + right) / 2;
if(left > right){
return list;
}else {
if(arr[mid] > value){
//向左进行递归
return binerySearch2( arr, left, mid-1, value );
}
else if (arr[mid] < value){
//向右进行递归
return binerySearch2( arr, mid+1, right, value );
}
else {
list.add( mid );
//找到之后不要返回，向左扫描找到所有的值
int temp = mid - 1;
while(true){
if(temp < 0 || arr[temp] != value){
break;
}
list.add(temp);
temp--;
}
//找到之后不要返回，向左递归找到所有的值
temp = mid + 1;
while(true){
if(temp > arr.length-1 || arr[temp] != value){
break;
}
list.add(temp);
temp++;
}
return list;
}
}
}
3. 插值查找算法
插值查找的原理：
插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面我们讲的 value
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/对应前面的代码公式：int mid = left + (right – left) * (value– arr[left]) / (arr[right] – arr[left])
代码：
package Search;
public class InsertValueSearch {
public static void main(String[] args) {
int arr[] = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = i + 1;
}
int res = insertSearch( arr, 0, arr.length - 1, 100 );
System.out.println(res);
}
public static int insertSearch(int arr[], int left, int right, int value){
if(left > right || value < arr[0] || value > arr[arr.length - 1]){
return -1;
}
//利用公式求出mid
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
if(arr[mid] < value){
//向右递归
return insertSearch( arr, mid + 1, right, value );
}
else if(arr[mid] > value){
//向左递归
return insertSearch( arr, left, mid - 1, value );
}
else {
//找到该值
return mid;
}
}
}
4. 斐波那契查找算法（黄金分割法）
思路：
黄金分割： 黄金分割是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其比值约为0.618。这个比例被公认为是最能引起美感的比例，因此被称为黄金分割。
斐波那契查找原理：利用斐波那契数列改变中间节点mid的位置，mid位于黄金分割点附近。
由斐波那契数列 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的两段，即如图所示。从而中间位置为mid=low+F(k-1)-1
类似的，每一子段也可以用相同的方式分割
但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可
代码：
package Search;
import java.util.Arrays;
public class fibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int arr[] = { 1,9,11,90,1000,1500};
System.out.println(fibSearch( arr,5646456 ));
}
//构建斐波那契数列
public static int[] fib(){
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < maxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
//编写斐波那契查找算法
public static int fibSearch(int arr[],int key){
int low = 0;
int high = arr.length - 1;
int k = 0; //表示斐波那契分割数值的下标
int mid = 0;
int f[] = fib(); //获取斐波那契数列
//获取斐波那契分割数值得下标
while(high > f[k] - 1 ){
k ++;
}
//因为f[k]的值可能大于数组的长度，所以重新构造一个数组，并且指向arr
int[] temp = Arrays.copyOf(arr, f[k]);
//使用arr数组的最后一个数填充temp
for (int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
//使用while循环查找的数key
while(low <= high){
//条件满足一直找
mid = low + f[k-1] - 1;
if(key < temp[mid]){
//向左边查找
high = mid - 1;
k--;
}else if(key > temp[mid]){
//向右边查找
low = mid + 1;
k = k - 2;
}else {
//找到
//确定哪个是下标
if(mid <= high){
return mid;
}else{
return high;
}
}
}
return -1;
}
}
总结
本文简单的阐述了4中基本的查找算法。分别介绍了线性查找算法，二分查找算法，插值查找算法，斐波那契查找算法的基本思路以及使用代码进行了实现。
查找算法有很多种，每一种都有各自的优缺点。在写代码的过程中，首先脑子中得有这些基本算法的印象，遇到复杂的问题时，要学会选择正确的算法，以便让我们的代码性能更好。
