01. 二分搜索篇

TIP

二分搜索，又称折半查找，一种在有序数组中查找目标元素的搜索算法。所以下面代码中的 nums 都假定已经从小到大排好序了。

1. 基础二分搜索

const searchInsert = function (nums, target) {
  let low = 0, high = nums.length - 1
  while (low <= high) {
    let mid = (low + high) >> 1
    if (nums[mid] === target) {
      return mid
    }
    if (nums[mid] < target) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 查找插入位置

只需修改基础版本的一行代码。

function searchInsert(nums: number[], target: number): number {
  let [low, high] = [0, nums.length - 1]
  while (low <= high) {
    const mid = (low + high) >> 1
    if (nums[mid] === target) return mid
    if (nums[mid] > target) high = mid - 1
    else low = mid + 1
  }
  return low // 相比于基础二分搜索，这里返回的是插入位置
}

1
2
3
4
5
6
7
8
9
10

3. 查找左边界

TIP

所谓查找左边界，就是在数组中查找最左边位置的目标元素。例如在 [-1, 1, 1, 1, 2] 中查找 1，应该返回下标 1。

// 寻找左边界
const getLeftBorder = (nums, target) => {
  let l = 0, r = nums.length - 1
  while (l <= r) {
    let mid = l + Math.floor((r - l) / 2)
    if (nums[mid] === target) {
      // 把右范围 r 一直向左逼近，直到到达 target 的左边界
      r = mid - 1
    } else if (nums[mid] < target) {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }
  // 1、若 target 大于数组中所有元素，则 l 一直右移，最后 l>=nums.length
  // 2、若 target 小于数组中所有元素，则 l = 0；
  // 3、剩下一种情况是 target 在 nums 中，结合2、3则判断 nums[l] !== target
  if (l >= nums.length || nums[l] !== target) {
    // 不存在 target
    return -1
  }
  return l
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 查找右边界

TIP

所谓查找右边界，就是在数组中查找最右边位置的目标元素。例如在 [-1, 1, 1, 1, 2] 中查找 1，应该返回下标 3。

// 寻找右边界
const getRightBorder = (nums, target) => {
  let l = 0, r = nums.length - 1, mid = 0
  while (l <= r) {
    mid = l + Math.floor((r - l) / 2)
    if (nums[mid] === target) {
      // 把左边范围 l 往右边逼近，直到到达 target 的右边界
      l = mid + 1
    } else if (nums[mid] < target) {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }
  // 1、若 target 小于数组中所有元素，则 r 一直左移，最后 r<0
  // 2、若 target 大于数组中所有元素，则 r = nums.length-1；
  // 3、剩下一种情况是 target 在 nums 中，结合2、3则判断 nums[r] !== target
  if (r < 0 || nums[r] !== target) {
    // 不存在 target
    return -1
  }
  return r
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5. 二分法求平方根

时间复杂度为 O(log(x)) 的算法。

function mySqrt(x: number): number {
  if (x === 1) return 1
  let [min, max] = [0, x]
  while (max - min > 1) {
    let mid = Math.floor((max + min) / 2)
    if (mid > x / mid) {
      max = mid
    } else {
      min = mid
    }
  }
  return min
}

1
2
3
4
5
6
7
8
9
10
11
12
13

01. 二分搜索篇 #

1. 基础二分搜索 #

2. 查找插入位置 #

3. 查找左边界 #

4. 查找右边界 #

5. 二分法求平方根 #