参阅基础

简介

二分搜索通常用于在有序的区间内寻找某个目标。如果区间内存在多个目标，还可以区分为寻找左侧边界的二分搜索和寻找右侧边界的二分搜索。

最基本的二分搜索算法：

1
2
3
4
5
6
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid + 1 和 right = mid - 1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回

寻找左侧边界的二分搜索：

1
2
3
4
5
6
7
因为我们初始化 right = nums.length -1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid + 1 和 right = mid - 1
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界

寻找右侧边界的二分搜索：

1
2
3
4
5
6
7
因为我们初始化 right = nums.length -1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid + 1 和 right = mid - 1
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

代码框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    }
  }
  return -1;
}

function leftBoundSearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    }
  }
  // target 比所有数都大
  if (left >= nums.length) return -1;
  // 类似之前算法的处理方式
  return nums[left] === target ? left : -1;
}

function rightBoundSearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      left = mid + 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    }
  }
  // target 比所有元素都小
  if (right < 0) return -1;
  // 类似之前算法的处理方式
  return nums[right] === target ? right : -1;
}

计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大，直接相加导致溢出的情况。

此外，尤其要注意 mid 为小数的情况，用 Math.floor 和 Math.ceil 处理得到的新区间是不同的。

相关习题

LeetCode 704. 二分查找

题目

来源：https://leetcode.cn/problems/binary-search/submissions/
难度：简单

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0,right = nums.length - 1;
    
    while(left <= right){
        let mid = Math.floor(left + (right-left) / 2);
        if(nums[mid] == target){
            return mid //返回对应元素索引
        }else if(nums[mid] < target){
            left = mid + 1
        }else if(nums[mid] > target){
            right = mid - 1 
        }
    }

    return -1
};