二分查找是一種在有序數(shù)組中查找元素的算法，通過不斷將搜索區(qū)域分成兩半來實現(xiàn)。你可能在日常生活中已經(jīng)不知不覺地使用了大腦里的二分查找。

最常見的例子是在字典中查找一個單詞。假設(shè)你想找到“馬拉松”的定義。你不會從字典的開頭開始查找。你會打開字典大約在中間位置。如果你在‘T’處，你已經(jīng)過頭了。所以，你會調(diào)整并分割差距，縮小范圍直到找到“馬拉松”。

這個逐步排除的過程就是二分查找的要點，但是針對數(shù)組的情況。

線性查找 vs 二分查找

考慮一個從1到100的數(shù)字?jǐn)?shù)組，你需要在這個范圍內(nèi)找到一個特定的數(shù)字，就像玩一個猜數(shù)游戲。

線性查找

簡單的方法是使用一個簡單的for循環(huán)——遍歷數(shù)組中的每個元素直到找到目標(biāo)項。

function findItem(arr, item) {
  for (let i = 0; i < arr.length; i++) {  
    if (arr[i] === item) {  
      return i;  
    }
  }
  return -1; // 未找到項
}

這個方法可以找到，但它的時間復(fù)雜度是O(n)；想象一下，如果你要找的數(shù)在1到1萬億之間。

你可以比線性查找做得更好。

二分查找

使用二分查找，不是檢查每個元素，而是從中間開始。如果你要找的數(shù)字更大，你向右走；如果更小，你向左走。

然后呢？你重復(fù)這個過程。中間，左邊或右邊，縮小可能性直到找到數(shù)字。

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while(left <= right) {
    let mid = Math.floor((left + right) / 2);
    if(arr[mid] === target) return mid;
    if(arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

它不僅能迅速切入數(shù)據(jù)；時間復(fù)雜度為O(logN)，比線性搜索快得多。

在空間方面，它是O(1)。不需要額外的存儲空間。

小結(jié)：何時使用二分查找？

二分查找最常用于數(shù)組，但也可以應(yīng)用于數(shù)據(jù)庫中的有序序列、排序鏈表中的搜索算法，甚至決策過程中可以預(yù)測和系統(tǒng)地劃分范圍的情況。

重要的是，二分查找只能在排序的項目集合上執(zhí)行。整個二分查找的方法基于這樣一個原則，即集合是按順序排列的，這樣算法才能通過比較中間項來預(yù)測搜索項的位置。如果集合沒有排序，這種預(yù)測就不起作用，算法也不能正確運行。