從一個例子開始，兩個人進行猜數游戲，其中一個人寫下一個數字，另外一個人猜，每猜一個數，給這個人說大了還是小了，繼續猜，比如猜一個100以內的數，寫下的數是64，最多猜7次就可以猜到這個數，這里就使用了二分思想， 二分思想是一個應用很廣泛的思想，比如對于一個有序陣列，它能將查找效率從O(n)優化到O(logn)，因為每次可以將范圍縮小為上一次的一半，這是在陣列中的應用場景，我們以這個為基礎來分析一下二分查找的時間復雜度 對于一個有 n 個元素的有序陣列中，每次查找后縮小資料范圍為上一次的二分之一，所以有 n/2 , n/4 , n/8, … , n/(2^k) 當 n/(2^k) = 1 時，得到最終結果，則 k = logn，記作二分查找的時間復雜度 O(logn)，是一個非常高效的演算法；舉個例子，如果我們在一個40億的資料中查找某個數，也只需要32次，相對于順序查找效率提升了太多，可見其威力， 總結一下，二分查找是針對一個有序集合，每次通過將要查找的資料范圍縮小為上一次的一半，直到找到目標值，或者區間縮小為0，二分查找正是在有序陣列上應用了二分思想， 二分思想其實是一種解決問題的思想，為了加速查找效率而生，所謂的二分并不代表一定是二，也可以是三，可以是N，只是一種表述，表達的意思是以最快的速率將搜索資料的范圍縮小，
二分思想在有序陣列上的應用及其變形
二分細想在陣列上的實作演算法是二分查找，二分查找的一般實作，有幾個需要注意的點 1 public class BinarySearch {
2 // 二分查找實作
3 public static int search(int[] arr, int target) {
4 int low = 0, high = arr.length - 1;
5
6 // 這里的中止條件是 low <= high, 因為 high = arr.length - 1
7 while (low <= high) {
8 // 使用 low + (high - low) / 2, 而不使用 (high + low) / 2, 是因為 high + low 可能造成整型溢位
9 // int mid = low + (high - low) / 2; // 這種方式是可以的，不如位運算效率高
10 int mid = low + ((high - low) >> 1); // 這種方式是最優的，效率最高
11
12 if (arr[mid] == target) {
13 return mid;
14 } else if (arr[mid] > target) {
15 high = mid - 1;
16 } else {
17 low = mid + 1;
18 }
19 }
20 return -1;
21 }
22
23 // 利用遞回實作二分查找
24 public static int searchRecursive(int[] arr, int target) {
25 return recurSearch(arr, target, 0, arr.length - 1);
26 }
27 private static int recurSearch(int[] arr, int target, int left, int right) {
28 // terminator
29 if (left > right)
30 return -1;
31
32 int mid = left + ((right - left) >> 1);
33
34 if (arr[mid] == target) {
35 return mid;
36 } else if (arr[mid] > target) {
37 return recurSearch(arr, target, left, mid - 1);
38 } else {
39 return recurSearch(arr, target, mid + 1, right);
40 }
41 }
42 }
以上是一個常規的二分查找實作，這個陣列中沒有重復元素，查找給定值的元素，但是還有更難的：
- 查找第一個值等于給定值的元素位置
- 查找最后一個值等于給定值的元素位置
- 查找第一個大于等于給定值的元素位置
- 查找最后一個小于等于給定值的元素位置
這幾個問題的代碼都相對難寫，代碼實作如下：
1 class BinarySearchExt {
2 // 查找第一個值等于給定值的元素位置
3 public static int searchFirst(int[] arr, int target) {
4 int left = 0, high = arr.length - 1;
5
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 if (arr[mid] > target) {
9 right = mid - 1;
10 } else if (arr[mid] < target) {
11 left = mid + 1;
12 } else {
13 if (mid == 0 || arr[mid - 1] != target) return mid;
14 else high = mid - 1;
15 }
16 }
17
18 return -1;
19 }
20
21 // 查找最后一個值等于給定值的元素位置
22 public static int searchLast(int[] arr, int target) {
23 int left = 0, high = arr.length - 1;
24 while (left <= right) {
25 int mid = left + (right - left) / 2;
26 if (arr[mid] > target) {
27 right = mid - 1;
28 } else if (arr[mid] < target) {
29 left = mid + 1;
30 } else {
31 if ((mid == arr.length - 1) || (arr[mid + 1] != target)) return mid;
32 else left = mid + 1;
33 }
34 }
35 return -1;
36 }
37
38 // 查找第一個大于等于給定值的元素位置
39 public static int searchGte(int[] arr, int target) {
40 int left = 0, right = arr.length - 1;
41 while (left <= right) {
42 int mid = left + ((right - left) >> 1);
43 if (arr[mid] >= target) {
44 if ((mid == 0) || (arr[mid - 1] < target)) return mid;
45 else right = mid - 1;
46 } else {
47 left = mid + 1;
48 }
49 }
50 return -1;
51 }
52
53 // 查找最后一個小于等于給定值的元素位置
54 public static int searchLte(int[] arr, int target) {
55 int left = 0, right = arr.length - 1;
56 while (left <= right) {
57 int mid = left + ((right - left) >> 1);
58 if (arr[mid] <= target) {
59 if ((mid == arr.length - 1) || (arr[mid + 1] > target)) return mid;
60 else left = mid + 1;
61 } else {
62 right = mid - 1;
63 }
64 }
65 return -1;
66 }
67 }
做個總結，分析一下二分查找的應用場景：
- 二分查找依賴于順序表結構，如陣列；在鏈表上直接運用二分查找效率低
- 二分查找需要資料是有序的，亂序的資料集合中無法應用，因為沒有辦法二分；所以對于相對靜態的資料，排序后應用二分查找的效率還是很不錯的；而對于動態變化的資料集合，維護成本會很高
- 資料量太小，發揮不出二分查找的威力；但是如果比較操作比較耗時，還是推薦使用二分查找
- 資料量太大，記憶體放不下
延伸之鏈表上的二分思想應用
上面，我們分析說在鏈表上應用二分查找的效率很低，那么為什么呢？分析一下
假設有n個元素的有序鏈表，現在用二分查找搜索資料，第一次移動指標次數 n/2，第二次移動 n/4，一直到 1，所以總的移動次數相加就是 n-1 次 可見時間復雜度是 O(n), 這個和順序查找鏈表的時間復雜度 O(n) 是同級別的，其實二分查找比順序查找的效率更低，因為它做了更多次無謂的指標移動
我們知道了二分思想直接應用到鏈表上是不可行的，有沒有其他的辦法，其實有，就是為有序鏈表增加多級索引，在搜索的時候根據索引應用二分思想，
跳表就是這樣一種資料結構，它既可以維護鏈表的有序性，還可以動態更新洗掉資料，而且提供了 O(logn) 時間復雜度，但是相比于鏈表的 O(1) 空間復雜度，跳表是 O(n) 的時間復雜度，跳表如下：
- 動態插入一個資料 O(logn)
- 動態洗掉一個資料 O(logn)
- 查找一個資料 O(logn)
- 按照區間查找資料 O(logn)
- 迭代輸出有序序列
- 選取跳表的最大索引層次以及如何選取多少個節點提取一個上級索引？一般情況下是選取16層/32層/64層，可根據實際的資料和應用常見來選擇，以免層數太少，資料量太大導致退化到鏈表的時間復雜度；此外，每個節點要建立幾級索引，一般的做法是使用一個隨機函式，這個函式要夠隨機，通過隨機函式的計算得到該節點的最大層數
- 在洗掉和插入資料時，跳表需要動態維護索引和資料，要盡量保證索引大小和資料大小的平衡性
- 此外，和紅黑樹相比，跳表的實作難度要小于紅黑樹，代碼實作更加可讀、不易出錯，同時還更加靈活，通過改變索引構建策略有效平衡執行效率和記憶體消耗
1 public class SkipList implements Printer { 2 private final static int MAX_LEVEL = 16; 3 private final static double SKIPLIST_P = 0.5; 4 5 private Node head = new Node(); 6 private int levelCnt = 1; 7 8 // 插入 9 public void insert(int score) { 10 int level = randomLevel(); 11 Node newNode = new Node(); 12 newNode.score = score; 13 newNode.maxLevel = level; 14 15 // update，記錄每一層的指標，方便對每一層做更新 16 Node[] update = new Node[level]; 17 for (int i = 0; i < level; i++) { 18 update[i] = head; 19 } 20 21 Node p = head; 22 for (int i = level - 1; i >= 0; i--) { 23 while (p.forwards[i] != null && p.forwards[i].score < score) { 24 p = p.forwards[i]; 25 } 26 // 找到每一層合適的插入位置 27 update[i] = p; 28 } 29 30 for (int i = 0; i < level; i++) { 31 // update[i] 指向 head or 第 i 層的 合適位置 的索引 32 // update[i].forwards[i] 相當于 head.forwards[i] 33 // 修改指標，讓newNode插入update[i]后面 34 newNode.forwards[i] = update[i].forwards[i]; 35 update[i].forwards[i] = newNode; 36 } 37 38 // update the skip list node level 39 if (levelCnt < level) { 40 levelCnt = level; 41 } 42 } 43 44 // 洗掉 45 public void delete(int score) { 46 Node[] update = new Node[levelCnt]; 47 Node p = head; 48 for (int i = levelCnt - 1; i >= 0; i--) { 49 while (p.forwards[i] != null && p.forwards[i].score < score) { 50 p = p.forwards[i]; 51 } 52 update[i] = p; 53 } 54 55 if (p.forwards[0] != null && p.forwards[0].score == score) { 56 for (int i = levelCnt - 1; i >= 0; i--) { 57 if (update[i].forwards[i] != null && update[i].forwards[i].score == score) { 58 update[i].forwards[i] = update[i].forwards[i].forwards[i]; 59 } 60 } 61 } 62 63 while (levelCnt > 1 && head.forwards[levelCnt - 1] == null) { 64 levelCnt--; 65 } 66 } 67 68 // 查找 69 public Node find(int score) { 70 Node p = head; 71 for (int i = levelCnt - 1; i >= 0; i--) { 72 while (p.forwards[i] != null && p.forwards[i].score < score) { 73 p = p.forwards[i]; 74 } 75 } 76 77 if (p.forwards[0] != null && p.forwards[0].score == score) { 78 return p.forwards[0]; 79 } 80 81 return null; 82 } 83 84 // 隨機函式 85 // 要保證隨機性 86 // 50% 回傳 1 87 // 25% 回傳 2 88 // 12.5% 回傳 3 89 // ... 90 private int randomLevel() { 91 int level = 1; 92 while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) { 93 level += 1; 94 } 95 return level; 96 } 97 98 // 順序輸出所有元素 99 @Override 100 public void print() { 101 Node p = head; 102 System.out.println("-----"); 103 while (p.forwards[0] != null) { 104 System.out.println(p.forwards[0]); 105 p = p.forwards[0]; 106 } 107 System.out.println("-----"); 108 } 109 110 class Node { 111 private String key; // 暫不使用 112 113 // 根據 score 進行排序 114 private int score; 115 116 private Node[] forwards; 117 private int maxLevel; 118 119 public Node() { 120 this(-1, MAX_LEVEL, 0); 121 } 122 123 public Node(int score, int maxNodeLevel, int maxLevel) { 124 this.score = score; 125 this.forwards = new Node[maxNodeLevel]; 126 this.maxLevel = maxLevel; 127 } 128 129 @Override 130 public String toString() { 131 StringBuilder sb = new StringBuilder(); 132 sb.append("{ score: "); 133 sb.append(score); 134 sb.append(", levels: "); 135 sb.append(maxLevel); 136 sb.append(" }"); 137 return sb.toString(); 138 } 139 } 140 }
跳表是一個高性能的資料結構，在Redis中得到了應用，Redis 的有序集合的底層資料結構就有用到跳表(Skiplist)；
二分查找常見的演算法題目
搜索插入位置，這是一道二分查找的直接應用 實作如下 1 class Solution {
2 public int searchInsert(int[] nums, int target) {
3 int left = 0, right = nums.length - 1;
4
5 int pos = -1;
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 if (nums[mid] == target) {
9 pos = mid;
10 break;
11 } else if (nums[mid] > target) {
12 right = mid - 1;
13 } else {
14 left = mid + 1;
15 }
16 }
17 return pos == -1 ? left : pos;
18 }
19 }
搜索二維矩陣 搜索二維矩陣II 有序矩陣中第K小的元素 兩數相除 搜索旋轉排序陣列 這個題目也是二分查找的一個拓展題目，代碼實作如下
1 class Solution {
2 public int search(int[] nums, int target) {
3 if (nums.length == 1) return nums[0] == target ? 0 : -1;
4 int low = 0, high = nums.length - 1;
5
6 while (low <= high) {
7 int mid = low + (high - low) / 2;
8
9 if (nums[mid] == target) return mid;
10
11 // 這里是關鍵
12 // nums[low] <= target && target < nums[mid] 表示 low mid 是有序的，且target在它們中間，需要將high向前移動
13 // nums[low] > nums[mid] && target > nums[high] 表示 low ~ mid 是無序的，而且 target 比 high 位置的元素還要大，因為 mid ~ high 是有序的，所以必然在 low ~ mid 中間，移動high
14 // nums[low] > nums[mid] && target < nums[mid] 表示 low ~ mid 是無序的, 而且 target 比mid位置處的值還要小，因為 mid ~ high 是有序的，所以必然在 low ~ mid 中間，移動high
15 // 否則，就是移動low
16 if ((nums[low] <= target && target < nums[mid]) ||
17 (nums[low] > nums[mid] && target > nums[high]) ||
18 (nums[low] > nums[mid] && target < nums[mid])) {
19 // 這里是
20 high = mid - 1;
21 } else {
22 low = mid + 1;
23 }
24 }
25
26 return low == high && nums[low] == target ? low : -1;
27 }
28 }
搜索旋轉排序陣列II
在排序陣列中查找元素的第一個位置和最后一個位置
Pow(x,n)
x的平方根，如果是精確到小數后6位呢？
有效的完全平方數
尋找旋轉排序陣列中的最小值
1 class Solution {
2 // 關鍵是邊界
3 public int findMin(int[] nums) {
4 int low = 0, high = nums.length - 1;
5 int lastElement = nums[high];
6 while (low < high) {
7 int mid = low + ((high - low) >> 1);
8 // 比最后一個元素小，說明轉折點必定在mid的左邊, 搜索左邊
9 if (nums[mid] < lastElement) high = mid;
10 // 否則在右邊
11 else low = mid + 1;
12 }
13 return nums[low];
14 }
15 }
尋找峰值
長度最小的子陣列
完全二叉樹的節點個數
二叉搜索樹第K小的元素
尋找重復數
最長上升子序列
兩個陣列的交集
兩個陣列的交集II
尋找右區間
找到K個最接近的元素
基于時間的鍵值存盤
在D天內送達包裹的能力
有效括號的嵌套深度
元素和小于等于閾值的正方形的最大邊長
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/107636.html
標籤：其他
上一篇：795. 前綴和（一維前綴和）