skyitachi's blog二分法的两种实现 2020-04-14

前言

虽然二分搜索很简单（在无重复的有序数组上）,但是也有很多值得注意的地方，而且有两种完全不同的写法（两种完全不同的功能）

lower bound

找出大于等于target的最小数组下标, 不存在的情况下返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func lower_bound(a []int, target int) int {
  l := 0
  h := len(a) - 1
  for l < h {
    m := l + (h - l) / 2
    if a[m] >= target {
      h = m
    } else {
      // l肯定可以取到h值，所以不需要使用向上取整计算m值
      l += 1
    }
  }
  if a[l] >= target {
    return l
  }
  return -1
}

upper bound

找出小于等于target的最大数组下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func upper_bound(a []int, target int) int {
  l := 0
	h := len(a) - 1
	for l < h {
		m := l + (h - l + 1) / 2
		if a[m] <= target {
      // l 要能够取到h值，就必须保证m使用向上取整计算, (h - l + 1) / 2 就是这么来的
			l = m
		} else {
			h = m - 1
		}
	}
	if a[l] <= target {
		return l
	}
	return -1
}

注意点

  • 计算mid的时候不能发生溢出
  • 数组下标不能越界
▲