快捷導(dǎo)航

JS實(shí)現(xiàn)二分查找的示例代碼

更新時(shí)間：2023年11月23日 09:10:18 作者：CreatorRay

二分查找也稱折半查找,它是一種效率較高的查找方法,本文主要介紹了JS實(shí)現(xiàn)二分查找的示例代碼,具有一定的參考價(jià)值,感興趣的可以了解一下

最近在面試的時(shí)候被問到手寫實(shí)現(xiàn)二分查找，雖然二分查找很早就聽過，也知道實(shí)現(xiàn)原理，但是手?jǐn)]起來，總是差點(diǎn)意思，正好復(fù)習(xí)一下。作為前端程序員，可能面試絕大部分公司不需要能寫很復(fù)雜的算法問題，但是這些基本的數(shù)據(jù)結(jié)構(gòu)和常見算法，還是得能手?jǐn)]出來。

什么是二分查找

二分查找是一種在有序數(shù)組中查找目標(biāo)元素的算法，它的基本思想是每次比較數(shù)組的中間元素和目標(biāo)元素，如果相等則返回中間元素的索引，如果不相等則根據(jù)比較結(jié)果縮小查找范圍，直到找到目標(biāo)元素或者查找范圍為空。二分查找的時(shí)間復(fù)雜度是O(log n)，其中n是數(shù)組的長(zhǎng)度，它比順序查找的時(shí)間復(fù)雜度O(n)要快得多。

如何實(shí)現(xiàn)二分查找

下面是用js語言實(shí)現(xiàn)二分查找的代碼示例，其中arr是有序數(shù)組，target是要查找的元素，函數(shù)返回target在arr中的索引，如果不存在則返回-1。

// 定義二分查找函數(shù)
function binarySearch(arr, target) {
  // 定義查找范圍的左右邊界
  let left = 0;
  let right = arr.length - 1;
  // 當(dāng)左邊界小于等于右邊界時(shí)，繼續(xù)查找
  while (left <= right) {
    // 計(jì)算中間元素的索引
    let mid = Math.floor((left + right) / 2);
    // 如果中間元素等于目標(biāo)元素，返回索引
    if (arr[mid] === target) {
      return mid;
    }
    // 如果中間元素小于目標(biāo)元素，說明目標(biāo)元素在右半部分，將左邊界移動(dòng)到中間元素的右邊
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    // 如果中間元素大于目標(biāo)元素，說明目標(biāo)元素在左半部分，將右邊界移動(dòng)到中間元素的左邊
    else {
      right = mid - 1;
    }
  }
  // 如果查找范圍為空，說明目標(biāo)元素不存在，返回-1
  return -1;
}

// 測(cè)試代碼
let arr = [1, 3, 5, 7, 9, 11, 13, 15]; // 定義一個(gè)有序數(shù)組
let target = 9; // 定義要查找的元素
let index = binarySearch(arr, target); // 調(diào)用二分查找函數(shù)
console.log(index); // 輸出結(jié)果，應(yīng)該是4

二分查找的實(shí)現(xiàn)原理

首先，定義查找范圍的左右邊界，初始時(shí)為整個(gè)數(shù)組的范圍，即左邊界為0，右邊界為數(shù)組的長(zhǎng)度減1。
然后，計(jì)算查找范圍的中間元素的索引，可以用左邊界加右邊界除以2的下取整來得到，例如，如果左邊界是0，右邊界是7，那么中間元素的索引是(0+7)/2=3.5，下取整是3。
接著，比較中間元素和目標(biāo)元素，如果相等，說明找到了目標(biāo)元素，返回中間元素的索引；如果不相等，說明目標(biāo)元素在中間元素的左邊或者右邊，需要縮小查找范圍。
如果中間元素小于目標(biāo)元素，說明目標(biāo)元素在中間元素的右邊，那么將左邊界移動(dòng)到中間元素的右邊，即左邊界等于中間元素的索引加1，右邊界不變，這樣就縮小了查找范圍的一半；如果中間元素大于目標(biāo)元素，說明目標(biāo)元素在中間元素的左邊，那么將右邊界移動(dòng)到中間元素的左邊，即右邊界等于中間元素的索引減1，左邊界不變，同樣縮小了查找范圍的一半。
重復(fù)第2步到第4步，直到找到目標(biāo)元素或者查找范圍為空，如果查找范圍為空，說明目標(biāo)元素不存在，返回-1。