在 JavaScript 中實現二分查詢，如果存在要搜尋的數字，則返回其索引

我們需要編寫一個 JavaScript 函式，這個函式將一個排序後的數字陣列作為第一個引數，將一個搜尋數字作為第二個引數。

如果搜尋數字在陣列中存在，我們需要在陣列中返回其索引，否則我們需要返回 -1。

我們必須充分利用二分查詢演算法來完成此操作。二分查詢演算法基本上是一種分治演算法，它將陣列遞迴地分成兩半，直到它轉換為一個單例元素。

二分查詢演算法在這種情況下對陣列進行排序是必要的，因為它讓我們很容易決定要分割哪一部分。

示例

const arr = [-3, -1, 4, 7, 9, 11, 14, 22, 26, 28, 36, 45, 67, 78, 88, 99];
const binarySearch = (arr = [], num) => {
   let l = 0;
   let r = arr.length - 1;
   while(l <= r){
      const mid = Math.floor((l + r) / 2); if(num == arr[mid]){
         return mid;
      }
      else if(num < arr[mid]){
         r = mid - 1;
      }
      else{
         l = mid + 1;
      };
   };
   return -1
};
console.log(binarySearch(arr, 22));
console.log(binarySearch(arr, 56));
console.log(binarySearch(arr, 11));

輸出

而控制檯中的輸出將是 −

7
-1
5

更新於: 2020 年 11 月 21 日

572 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告