二分查找（Binary Search）是一種在有序陣列中查找目標元素的查找演算法，它的基本思路是：在陣列的中間元素開始，如果該元素等于目標元素，則查找成功；如果該元素大于目標元素，則在左半部分繼續查找；如果該元素小于目標元素，則在右半部分繼續查找，這樣一直重復這個程序，直到查找成功或者查找失敗，
基本步驟：
-
設定兩個指標，left 和 right，分別指向陣列的第一個元素和最后一個元素，
-
計算中間索引，mid = (left + right) / 2，
-
如果該索引上的元素等于目標元素，則查找成功，回傳該索引，
-
如果該索引上的元素大于目標元素，則說明目標元素在左半部分，將 right 指標移動到 mid-1，
-
如果該索引上的元素小于目標元素，則說明目標元素在右半部分，將 left 指標移動到 mid+1，
-
重復步驟2-5，直到查找成功或者 left > right，
-
如果查找失敗，則回傳 -1，
二分查找的時間復雜度是 O(log n)，比順序查找和線性查找的時間復雜度更優秀，但是，需要注意的是，二分查找只能用于有序陣列，
JavaScript 實作二分查找可以使用遞回或迭代兩種方法，
這是一個使用遞回實作二分查找的示例代碼：
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1;
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] > target) {
return binarySearch(arr, target, left, mid - 1);
} else {
return binarySearch(arr, target, mid + 1, right);
}
}這是一個使用迭代實作二分查找的示例代碼：
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}在上面的代碼中，我們可以看到，遞回和迭代兩種方法都是基于同樣的思想，不斷地將查找范圍縮小，直到找到目標元素或者縮小到不可能找到目標元素的范圍，
兩種方法的區別在于，遞回方法是使用函式呼叫堆疊來保存狀態，而迭代方法是使用回圈和變數來保存狀態，對于大部分情況來說，迭代方法更加高效，因為它避免了函式呼叫堆疊的開銷，
兩種方法都需要注意的是陣列是有序的，且需要先確定好左右邊界，
這里的代碼只是一個簡單的二分查找示例，在實際使用中，還需要根據具體需求進行調整和優化，
作者：yuzhihui
出處：http://www.cnblogs.com/yuzhihui/ 宣告：歡迎任何形式的轉載，但請務必注明出處！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/541960.html
標籤：JavaScript