基本介紹

1.二分查找只適用于從有序的數列中進行查找(比如數字和字母)，將數列排序后再進行查找。

2.二分查找法的運行時間為對數時間O(log2n),即查找到需要的目標位置最多只需log2n步，假設從[0,99]的隊列中尋找目標數30，則需要查找步數為log2(100)，即最多需要7次(2^6<100<2^7)。

代碼案例

1. package com.xie.algorithm; 
2.  
3. public class BinarySearchNoRecur { 
4.     public static void main(String[] args) { 
5.         int[] arr = {1, 3, 8, 10, 11, 67, 100}; 
6.         int index = binarySearch(arr, 1); 
7.         System.out.println("index = " + index); 
8.     } 
9.  
10.     /** 
11.      * 二分查找非遞歸實現 
12.      * 
13.      * @param arr    待查找的數組,arr是升序排列 
14.      * @param target 需要查找的數 
15.      * @return 返回對應的下標 ，-1 表示沒有找到 
16.      */ 
17.     public static int binarySearch(int[] arr, int target) { 
18.         int left = 0; 
19.         int right = arr.length - 1; 
20.         while (left <= right) { 
21.             int mid = (left + right) / 2; 
22.             if (arr[mid] == target) { 
23.                 return mid; 
24.             } else if (arr[mid] > target) { 
25.                 //需要向左邊查找 
26.                 right = mid - 1; 
27.  
28.             } else { 
29.                 //需要向右邊查找; 
30.                 left = mid + 1; 
31.             } 
32.         } 
33.         return -1; 
34.     } 
35. } 

基本介紹

1.插值查找算法類似于二分查找，不同的是插值查找每次從自適應的mid處開始查找。

2.二分查找中求mid索引的公式轉成插值查找mid索引公式，low表示左邊的索引，high表示右邊的索引，key表示要查找的值

代碼案例

1. package com.xie.search; 
2.  
3. import java.util.ArrayList; 
4. import java.util.List; 
5.  
6. public class InsertValueSearch { 
7.     static int count = 0; 
8.  
9.     public static void main(String[] args) { 
10.         int[] arr = new int[102]; 
11.         arr[0] = 1; 
12.         arr[1] = 1; 
13.         for (int i = 2; i < 102; i++) { 
14.             arr[i] = i; 
15.         } 
16.         List<Integer> indexList = insertValueSearch(arr, 0, arr.length - 1, 1); 
17.         System.out.println("indexList = " + indexList); 
18.         System.out.println("查找次數：" + count); 
19.  
20.         /* 
21.         indexList = [1, 0] 
22.         查找次數：1 
23.          */ 
24.     } 
25.  
26.     /** 
27.      * 插值查找，返回索引集合 
28.      * 
29.      * @param arr       數組 
30.      * @param left      左邊索引 
31.      * @param right     右邊索引 
32.      * @param findValue 要查找的值 
33.      * @return 找到就返回所有索引的集合，沒有就返回空 
34.      */ 
35.     public static List<Integer> insertValueSearch(int[] arr, int left, int right, int findValue) { 
36.         count++; 
37.         List<Integer> indexList = new ArrayList<Integer>(); 
38.         //注意：findValue < arr[0] || findValue > arr[arr.length - 1] 這個必須要，否則mid可能越界 
39.         if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) { 
40.             return new ArrayList<Integer>(); 
41.         } 
42.         int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]); 
43.         int midValue = arr[mid]; 
44.  
45.         if (findValue > midValue) { 
46.             return insertValueSearch(arr, mid + 1, right, findValue); 
47.         } else if (findValue < midValue) { 
48.             return insertValueSearch(arr, left, mid - 1, findValue); 
49.         } else { 
50.             //如果找到了，再向左掃描，將滿足條件的加入indexList 
51.             int temp = mid - 1; 
52.             while (true) { 
53.                 if (temp < 0 || arr[temp] != findValue) { 
54.                     break; 
55.                 } 
56.                 indexList.add(temp); 
57.                 temp--; 
58.             } 
59.  
60.             //再向右掃描,將滿足條件的加入indexList 
61.             temp = mid + 1; 
62.             while (true) { 
63.                 if (temp > right || arr[temp] != findValue) { 
64.                     break; 
65.                 } 
66.                 indexList.add(temp); 
67.                 temp++; 
68.             } 
69.             indexList.add(mid); 
70.             return indexList; 
71.         } 
72.     } 
73. } 

注意事項

1. 對于數據量大，關鍵字分布比較均勻的查找表來說，采用插值查找，速度較快。
2. 關鍵字分布不均勻的情況下，該方法不一定比二分法要好。

原文地址：https://www.toutiao.com/i6939142586317799968/