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

什么是二分查找

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

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

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

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

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

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

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

總結(jié)

本文介紹了二分查找的定義、時間復雜度、實現(xiàn)原理和代碼示例。

二分查找是一種在有序數(shù)組中查找目標元素的算法，它的時間復雜度是O(log n)，比順序查找的時間復雜度O(n)要快得多。

二分查找的實現(xiàn)原理是每次比較數(shù)組的中間元素和目標元素，如果相等則返回中間元素的索引，如果不相等則根據(jù)比較結(jié)果縮小查找范圍，直到找到目標元素或者查找范圍為空。

到此這篇關(guān)于JS實現(xiàn)二分查找的示例代碼的文章就介紹到這了,更多相關(guān)JS 二分查找內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論