二分法查找，也稱作二分查找或折半查找，是一種在有序數(shù)組中快速查找特定元素的算法。它采用分治法思想，通過將問題劃分為規(guī)模更小的子問題，并且通過對子問題的查找來解決原問題。

二分法查找的思路是不斷地將數(shù)組一分為二，然后判斷目標(biāo)值在哪一部分，進而在該部分繼續(xù)進行二分查找。具體步驟如下：

1. 首先，設(shè)置左邊界 left 為0，右邊界 right 為數(shù)組的長度減1。
2. 然后，計算中間值 mid 為左邊界與右邊界的平均值，并取整。
3. 接著，比較中間值 arr[mid] 與目標(biāo)值 target 的大小。如果相等，則返回索引 mid。
4. 如果 arr[mid] 大于 target，說明目標(biāo)值在左半部分，將右邊界 right 更新為 mid-1。
5. 如果 arr[mid] 小于 target，說明目標(biāo)值在右半部分，將左邊界 left 更新為 mid+1。
6. 重復(fù)步驟2至5，直到左邊界大于右邊界，表示數(shù)組中無目標(biāo)值，返回-1。

說明：

• 開始時，初始化左指針l指向數(shù)組的首元素，右指針r指向數(shù)組的尾元素。
• 判斷左指針l是否大于右指針r，如果是則表示沒有找到目標(biāo)值，結(jié)束查找。
• 每次都取左指針l和右指針r中間的元素作為中間值。
• 判斷中間值是否等于目標(biāo)值，如果是則表示找到目標(biāo)值，結(jié)束查找。
• 如果中間值大于目標(biāo)值，說明目標(biāo)值在左半部分，更新右指針r為中間值的前一個位置，繼續(xù)查找。
• 如果中間值小于目標(biāo)值，說明目標(biāo)值在右半部分，更新左指針l為中間值的后一個位置，繼續(xù)查找。
• 繼續(xù)進行以上步驟，直到找到目標(biāo)值或者確定沒有目標(biāo)值。

示例代碼：

function binarySearch(arr, target) {
   let left = 0; // 定義左邊界指針為數(shù)組的起始位置
   let right = arr.length - 1; // 定義右邊界指針為數(shù)組的末尾位置

   while (left <= right) { // 當(dāng)左邊界指針小于等于右邊界指針時執(zhí)行循環(huán)
     let mid = Math.floor((left + right) / 2); // 計算中間元素的位置，向下取整

     if (arr[mid] === target) { // 如果中間元素等于目標(biāo)值
       return mid; // 返回中間元素的位置
     } else if (arr[mid] < target) { // 如果中間元素小于目標(biāo)值
       left = mid + 1; // 移動左邊界指針到中間元素的下一個位置
     } else { // 如果中間元素大于目標(biāo)值
       right = mid - 1; // 移動右邊界指針到中間元素的前一個位置
     }
   }

   return -1; // 如果循環(huán)結(jié)束仍未找到目標(biāo)值，則返回-1
}

// 示例使用
let arr = [1, 3, 5, 7, 9];
let target = 5;

let result = binarySearch(arr, target);
console.log(result); // 輸出 2

在上面的示例中，提供了一個有序數(shù)組 arr 和目標(biāo)值 target，然后調(diào)用 binarySearch 函數(shù)進行二分查找。最后輸出的結(jié)果為目標(biāo)值在數(shù)組中的索引，如果不存在則返回-1。文章來源地址http://www.zghlxwxcb.cn/news/detail-698258.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法之二分法查找的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！