二分查找

2024年03月14日

柏拉文

越努力，越幸运

一、认识

---

二分查找又叫折半查找。二分法查找的思想: 基于数组的有序性，每次都将当前的数组分为两半，通过关键字和中间元素的比较，立即排除掉其中不可能存在和键值相等的元素的那一半

1.1 公式

中间索引值公式: middle = Math.floor((start + end) / 2) 或者 middle = (start + end) / 2 或者 (start + end) >> 1

1.2 思路

在升序数组 nums 中寻找目标值 target，对于特定下标 i，比较 nums[i] 和 target 的大小:

• 如果 nums[i]=target, 则下标 i 即为要寻找的下标

• 如果 nums[i]>target, 则 target 只可能在下标 i 的左侧

• 如果 nums[i]<target, 则 target 只可能在下标 i 的右侧

基于上述事实，可以在有序数组中使用二分查找寻找目标值。

二分查找的做法是，定义查找的范围 [left,right], 初始查找范围是整个数组。每次取查找范围的中点 mid,比较 nums[mid] 和 target 的大小，如果相等则 mid 即为要寻找的下标，如果不相等则根据 nums[mid] 和 target 的大小关系将查找范围缩小一半。

由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 O(logn)，其中 n 是数组的长度。

二、实现

---

2.1 查找元素

查找元素: 给定一个足够空间的递增数组和一个定值, 查找定值在数组中的索引位置, 如果不存在返回 -1

function binarySearch(left, right, target, array) {
  let l = left;
  let r = right;
  while (l <= r) {
    const middle = (l + r) >> 1;
    const middleItem = array[middle];
    if (middleItem === target) {
      return middle;
    } else if (middleItem < target) {
      l = middle + 1;
    } else {
      r = middle - 1;
    }
  }
  return -1;
}

2.2 查找位置

查找位置: 给定一个足够空间的递增数组和一个定值, 将定值插入到数组中, 且保证递增。那么需要通过二分获取一个 left 值, 最后 array[left] = 定值 即可。

function binarySearch(left, right, target, array) {
  let l = left;
  let r = right;
  while (l < r) {
    const middle = (l + r) >> 1;
    const middleItem = array[middle];
    if (middleItem < target) {
      l = middle + 1;
    } else {
      r = middle;
    }
  }
  return l;
}