目录

• 查找算法
• • 1.线性(顺序)查找
  • • (1)思路
    • (2)代码实现(java)
  • 2.二分(折半)查找
  • • (1)思路
    • (2)代码实现(java)
  • 3.插值查找
  • • (1)思路
    • (2)代码实现(java)
  • 4.斐波那契(黄金分割法)查找
  • • (1)思路
    • (2)代码实现(java)

查找算法

1.线性(顺序)查找

(1)思路

判断序列中是否包含某个元素，找到提示并输出下标值
初始数组：{13,4,88,28,6}，找到88这个值的下标。

(2)代码实现(java)

/*** 顺序(线性)查找* author：xinxin*/
public class SeqSearch {public static void main(String[] args) {int[] arr = {13,4,88,28,6};int result = seqSearch(arr,88);System.out.println("下标为:"+result);}/*** @param arr  无序序列* @param value 需要找的值* @return*/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.二分(折半)查找

(1)思路

注意：二分查找的前提是序列是有序的。
初始数组：{1,2,3,4,5,6,7,8,9}，查找3这个值，并输出下标，没有就提示

(2)代码实现(java)

/*** 二分查找* author：xinxin*/
public class BinarySearch {public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9};List resValList = binarySearch(arr, 0, arr.length - 1, 3);System.out.println("要找的值下标为："+resValList);}/*** @param arr    初始数组* @param left   左索引* @param right  右索引* @param value  要找的值* @return*/public static List binarySearch(int[] arr, int left, int right, int value){//没找到值if (left > right){return new ArrayList();}int mid = (left + right) / 2;int midVal = arr[mid];//向右递归if (midVal < value){return binarySearch(arr,mid+1,right,value);}else if (midVal > value){//向左递归return binarySearch(arr,left,mid-1,value);}else{//正好找到了(包含出现多个相同的值)ArrayList resValList = new ArrayList<>();//向左扫描，看看是否存在相同的值int temp = mid - 1;while(true){if (mid < 0 || arr[temp] != value){//退出break;}resValList.add(temp);temp = temp - 1;//左移}//向右扫描，看看是否存在相同的值temp = mid + 1;while(true){if (mid > arr.length-1 || arr[temp] != value){//退出break;}resValList.add(temp);temp = temp + 1;//右移}resValList.add(mid);return resValList;}}
}

3.插值查找

(1)思路

插值查找类似于二分查找，不同的是每次都是mid处查找，对于数据量比较大，分布比较均匀，适合用插值查找。
公式：mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]) //left代表左索引，right代表右索引，value就是要查找的值
初始数组：[1,2,3…100]
找值 1 ， mid = 0 + (99 - 0) * (1 - 1) / (100 - 1) = 0
找值100，mid= 0 + (99 - 0)*(100 - 1)/(100 - 1) = 99

(2)代码实现(java)

/*** 插值查找* author：xinxin*/
public class InsertSearch {public static void main(String[] args) {int[] arr = new int[100];for (int i = 0; i < 100; i++) {arr[i] = i + 1;}int index = insertSearch(arr,0,arr.length-1,23);System.out.println("下标为："+index);}public static int insertSearch(int[] arr,int left,int right,int value){//要找的值不存在if (left > right || arr[left] < arr[0] || arr[right] > 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,left,mid-1,value);}else if (arr[mid] < value){//向右递归return insertSearch(arr,mid+1,right,value);}else{//正好找到return mid;}}
}

4.斐波那契(黄金分割法)查找

(1)思路

黄金分割：一条线段分割成两部分，其中一部分比上全长，接近0.618。
和前面两个相似，仅仅改变了中间结点(mid)，mid位于黄金分割点附近,mid = left + F(k-1)-1, F是斐波那契数列，k代表第几个元素。
斐波那契数列：{1,1,2,3,5,8,13} 从第三个元素开始，就是前两个数相加的值。
初始数组：{1,6,16,26,888,1234},使用斐波那契查找。

(2)代码实现(java)

/*** 斐波那契查找* author：xinxin*/
public class FibonacciSearch {static int  maxSize = 20;public static void main(String[] args) {int[] arr = {1,6,16,26,888,1234};int resVal = fibonacciSearch(arr,16);System.out.println("斐波那契查找下标为："+resVal);}/*** 生成一个斐波那契数组* @return*/public static int[] fib(){int[] fib = new int[maxSize];fib[0] = 1;fib[1] = 1;for (int i = 2; i < maxSize; i++) {fib[i] = fib[i-1] + fib[i-2];}return fib;}/*** @param arr   初始数组* @param value 要查找的值* @return 返回值，没找到返回 -1，找到返回下标*/public static int fibonacciSearch(int[] arr,int value){int left = 0;int right = arr.length-1;int k = 0; //斐波那契数值的下标int mid = 0;int[] fib = fib();//获取斐波那契数列//获取斐波那契分割数值下标while(right > fib[k] - 1){k++;}int[] temp = Arrays.copyOf(arr,fib[k]);for (int i = right + 1; i < temp.length; i++) {temp[i] = arr[right];}//找到我们要找的值while(left <= right){mid = left + fib[k-1] - 1;if (value < temp[mid]){//向左查找right = mid - 1;k--;}else if (value > temp[mid]){//向右查找left = mid + 1;k = k - 2;}else {//找到if (mid <= right){return mid;}else {return right;}}}return -1;}
}