一、基礎概念

1、Sorted（單調遞增or單調遞減）

2、Bounded(存在上下界)

3、Accessible by index（能夠通過索引訪問，數組適合，but鏈表不適合）

二分查找是一種在每次比較之后將查找空間一分為二的算法。每次需要查找集合中的索引或元素時，都應該考慮二分查找。如果集合是無序的，我們可以總是在應用二分查找之前先對其進行排序。

二分查找一般由三個主要部分組成：

1、預處理--如果有集合未排序，則進行排序。

2、二分查找--使用循環或遞歸在每次比較后將查找空間劃分為兩半

3、后處理--在剩余空間中確定可行的候選者

例如：給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下標為 4

示例 2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

提示：

1、你可以假設 nums 中的所有元素是不重復的。

2、n 將在 [1, 10000]之間。

3、nums 的每個元素都將在 [-9999, 9999]之間。

step01: 設定初始值 left和 right：

step02: 設定中間指針 mid = left + (right-left)/2：

step03：

step04：

step05：

step06：

step07：

二、通用模版

2.1 模版一

var binarySeach(nums,target){
  if(nums == null|| nums.length ==0){
    return -1;
  }
  let left =0,right=nums.length- 1; //初始條件
  while(left<=right){ //終止條件 left>right
    let mid = Math.floor(left + (right-left)/2); 
    if(nums[mid] == target){ 
      return mid;
    } else if(nums[mid]<target){
      left = mid + 1; //向右查找
    }else{
      right = mid - 1; //向左查找
    }
  }
  return -1;
}

關鍵屬性：

• 二分查找的最基礎和最基本的形式
• 查找條件可以在不與元素的兩側進行比較的情況下確定（或使用它周圍的特定元素）
• 不需要后處理，因為每一步中，你都在檢查是否找到了元素。如果到達末尾，則指導未找到該元素。

2.2 模版二

var binarySeach(nums,target){
  if(nums == null|| nums.length ==0){
    return -1;
  }
  
  let left =0,right=nums.length; //初始條件
  
  while(left<right){ //終止條件 left>=right
    let mid = Math.floor(left + (right-left)/2);  //阻止(left+right)溢出
    if(nums[mid] == target){ 
      return mid;
    } else if(nums[mid]<target){
      left = mid + 1; //向右查找
    }else{
      right = mid; //向左查找
    }
  }
  if(left !=nums.length && nums[left] == target) return left;
  return -1;
}

模版二：是二分查找的高級模板。它用于查找需要訪問數組中當前索引及其直接右鄰居索引的元素或條件。

關鍵屬性：

• 一種實現二分查找的高級方法
• 查找條件需要訪問元素的直接右鄰居
• 使用元素的右鄰居來確定是否滿足條件，并決定是向左還是向右
• 保證查找空間在每一步中至少有2個元素
• 需要進行后處理，當你剩下一個元素的時候，循環/遞歸結束。需要評估剩余元素是否符合條件

2.3 模版三

var binarySeach(nums,target){
  if(nums == null|| nums.length ==0){
    return -1;
  }
  
  let left =0,right=nums.length-1; //初始條件
  
  while(left+1 < right){ //終止條件 left+1 == right
    let mid = Math.floor(left + (right-left)/2);  //阻止(left+right)溢出
    if(nums[mid] == target){ 
      return mid;
    } else if(nums[mid]<target){
      left = mid; //向右查找
    }else{
      right = mid; //向左查找
    }
  }
  if(nums[left] == target) return left;
  if(nums[right] == target) return right;
  return -1;
}

模版3是二分法查找的另一種獨特形式。 它用于搜索需要訪問當前索引及其在數組中的直接左右鄰居索引的元素或條件。

關鍵屬性：

• 實現二分法查找的另一種方法
• 搜索條件需要訪問元素的直接左右鄰居
• 使用元素的鄰居來確定它是向右還是向左
• 保證查找空間在每個步驟中至少有3個元素
• 需要進行后處理。當剩下2個元素，循環/遞歸結束。

2.4、模版分析：

這三個模版的不同之處在于：

• 左、中、右索引的分配
• 循環或遞歸終止條件
• 后處理的必要性

其中模版一和模版三是最常用的， 幾乎所有二分查找問題都可以用其中之一親送實現。 模版二更高級一些， 用于解決某些類型的問題。

這 3 個模板中的每一個都提供了一個特定的用例：

模板 1 (left <= right)

• 二分查找的最基礎和最基本的形式。
• 查找條件可以在不與元素的兩側進行比較的情況下確定（或使用它周圍的特定元素）。
• 不需要后處理，因為每一步中，你都在檢查是否找到了元素。如果到達末尾，則知道未找到該元素。

模板 2 (left < right)

• 一種實現二分查找的高級方法。
• 查找條件需要訪問元素的直接右鄰居。
• 使用元素的右鄰居來確定是否滿足條件，并決定是向左還是向右。
• 保證查找空間在每一步中至少有 2 個元素。
• 需要進行后處理。 當你剩下 1 個元素時，循環 / 遞歸結束。 需要評估剩余元素是否符合條件。

模板 3 (left + 1 < right)

• 實現二分查找的另一種方法。
• 搜索條件需要訪問元素的直接左右鄰居。
• 使用元素的鄰居來確定它是向右還是向左。
• 保證查找空間在每個步驟中至少有 3 個元素。
• 需要進行后處理。 當剩下 2 個元素時，循環 / 遞歸結束。 需要評估其余元素是否符合條件。

三、復雜度計算

3.1、時間復雜度

O(log n) ：

因為二分查找是通過對查找空間中間的值應用一個條件來操作的，并因此將查找空間折半，在更糟糕的情況下，我們將不得不進行O(log n) 次比較， 其中n是集合中元素的數目。

為什么是log n?

• 二分查找是通過將現有數組一分為二來執行的
• 因此，每次調用子例程（或完成一次迭代）時，其大小都會減少到現有部分的一半。
• 首先N變成 N/2，然后又變成N/4，然后繼續下去，直到找到元素或尺寸變為1。
• 迭代的最大次數是log N(base2)。

第一次： n/2
第二次： n/2^2
第三次： n/2^3
...
第k次： n/2^k

3.2、空間復雜度

O(1)

雖然二分查找確實需要跟蹤 3 個指標，但迭代解決方案通常不需要任何其他額外空間，并且可以直接應用于集合本身，因此需要 O(1) 或常量空間。

四、二分查找的應用

• 二分調試法

把所有潛在的問題都用類似“數組二分查找”的方式把代碼遍歷一遍，不斷縮小問題的范圍，最終找到問題原因。

通過二分法，我們可以快速縮小問題范圍，這樣一來調試的效率也就上去了。

• Kafka 采用二分法找數據

二分查找相關系列題：