二分法查找——简介

二分法查找是一种常用的高效查找算法，也叫做二分查找或折半查找。它通过将已排好序的数据集从中间分成左右两部分，来逐步缩小查找范围，最终找到目标值。二分法查找的时间复杂度为O(logN)，比顺序查找的时间复杂度O(N)要快得多。

二分法查找的思路

二分法查找的核心思想是将已排序的数组分成三个区间：左区间、中间元素和右区间。在每一次查找中，将目标元素与中间元素进行比较，根据比较结果选择向左区间或右区间继续查找，直到找到目标元素或查找区间为空。

具体步骤如下：

1. 将目标值与数组的中间值进行比较
2. 如果目标值等于中间值，则查找成功
3. 如果目标值小于中间值，则在左区间进行下一轮查找
4. 如果目标值大于中间值，则在右区间进行下一轮查找
5. 重复上述步骤，直到找到目标值或查找区间为空

二分法查找的代码示例

/**
 * 二分法查找
 * @param array 排好序的数组
 * @param target 目标值
 * @return 目标值在数组中的索引，若不存在则返回-1
 */
function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

// 示例
const array = [1, 3, 5, 7, 9];
const target = 5;
const index = binarySearch(array, target);
console.log(`目标值${target}在数组中的索引为：${index}`);

以上是一个基础的二分法查找的代码示例，通过调用binarySearch函数可以实现对已排序数组的二分查找，并返回目标值在数组中的索引。

需要注意的是，二分法查找的前提是数组已经排好序，否则无法得到正确的结果。因此，在使用二分法查找之前，需要确保数组是有序的。