二分搜索

在有序數組中確定num存在還是不存在：

• 當arr[m] == num，則num存在
• 當arr[m] > num，則 r = m - 1，縮小r的范圍，繼續往左二分
• 當arr[m] < num，則l = m + 1，縮小l的范圍，繼續往右二分

// 保證arr有序，才能用這個方法
public static boolen exist(int[] arr, int num) {if (arr == null || arr.length == 0){return false;}int l = 0, r = arr.length - 1, m = 0;while (l <= r) {// 中間值m = l + ((r - l) >> 1);if (arr[m] == num) {// 中間值 == num，直接返回結果return true;} else if (arr[m] > num) {// 中間值 > num，縮小r的范圍r = m - 1;} else {// 中間值 < num, 縮小l的范圍l = m + 1;}}return false;
}

有序數組中找>=num的最左位置：

• ans(二分搜索法答案) 初始值設置為：-1，-1表示不存在符合要求的值
• 當middle(中點值) >= num 時修改ans = middle 并 r = middle - 1 縮小右邊范圍，繼續往左二分
• 當 middle(中點值) < num 時 不修改 ans 但 l = middle + 1 縮小左邊范圍 ，繼續往右二分
• 求中間值公式用：l + ((r - l) >> 1) 或者 l + ((r - 1) / 2)，防止運算數值溢出
• 找<=num的最左位置沒有意義，直接找下標為0的位置進行判斷就可以得出結果

// 保證arr有序，才能用這個方法
// 有序數組中找>=num的最左位置
public static int findLeft(int[] arr, int num) {int l = 0, r = arr.length - 1, m = 0;int ans = -1;while (l <= r){m = l + ((r - l) >> 1); // 等于 l + ((r - 1) / 2), 等于 (l + r) / 2if (arr[m] >= num) {ans = m;r = m - 1;} else {l = m + 1;}}return ans;
}

在有序數組中找<=num的最右位置：

• ans(二分搜索法答案) 初始值設置為：-1，-1表示不存在符合要求的值
• 當middle(中點值) <= num 時修改ans = middle 并 l = middle + 1 縮小右邊范圍，繼續往右二分
• 當 middle(中點值) > num 時 不修改 ans 但 r = middle - 1 縮小左邊范圍 ，繼續往左二分
• 求中間值公式用：l + ((r - l) >> 1) 或者 l + ((r - 1) / 2)，防止運算數值溢出

// 保證arr有序，才能用這個方法
// 有序數組中找<=num的最右位置
public static int findLeft(int[] arr, int num) {int l = 0, r = arr.length - 1, m = 0;int ans = -1;while (l <= r){m = l + ((r - l) >> 1); // 等于 l + ((r - 1) / 2), 等于 (l + r) / 2if (arr[m] <= num) {ans = m;l = m + 1;} else {r = m - 1;}}return ans;
}

二分搜索不一定發生在有序數組上（比如尋找峰值問題）：

• 峰值：i-1 < i > i+1，則i為峰值，如果右邊或者左邊沒數值可以認為是無窮小

• 數組條件：數組中相鄰的兩個數不相等， 只返回一個峰值就行

• 0位置不是峰值，N-1位置不是峰值，則呈現左邊上揚右邊下降的趨勢，這中間會出現一個或者多個峰值

• 計算步驟：

  1. 先判斷數組[0]是不是峰值，是則直接返回
  2. 再判斷數組[N-1]是不是峰值，是則直接返回
  3. 設置 L = 1，R = N-2，求中間值，如果中間值是峰值則直接返回
  4. 判斷中間值的大小，當左側數值>中間值，往左側二分，而右側數值>中間值，往右側二分，如果兩個都成立選其中一個就行

  // 峰值元素是指其嚴格大于左右相鄰值的元素
  // 給你一個整數數組 nums，已知任何兩個相鄰的值都不相等
  // 找到峰值元素并返回其索引
  // 數組可能包含多個峰值，在這種情況下，返回任何一個峰值 所在位置即可
  // 你可以假設 nums[-1] = nums[n] = 無窮小
  // 你必須實現時間復雜度為 0(log n) 的算法來解決此問題
  public static int findPeakElement(int[] arr) {int n = arr.length;// 小   小// -1 0 1if (arr.length == 1) {return 0;}// 數組長度 >= 2// 單獨驗證0位置，是不是峰值點if (arr[0] > arr[1]) {return 0;}//  單獨驗證n-1位置，是不是峰值點if (arr[n - 1] > arr[n - 2]) {return n - 1;}// X   中間一定有一個峰值    X// 0                      N-1// 中間 ：1 ~ n-2 ，一定有峰值點// 每一步的l...r : 一定有峰值點int l = 1, r = n - 2, m = 0, ans = -1;while (l <= r) {m = l + ((r - l) >> 1);if (arr[m - 1] > arr[m]) {r = m - 1;} else if (arr[m] < arr[m + 1]) {l = m + 1;} else {ans = m;break;}}return ans;
  }
  

某側必有對應的值或者某側必沒有對應的值，則可以使用二分搜索法

如果數組長度為n，那么二分搜索搜索次數是log n次，以2為底

二分搜索世界復雜度o(log n)