go 语言二分查找

1. lower_bound

在nums中查找第一个大于等于target的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
func lower_bound(nums []int, target int) int {
	l := 0
	r := len(nums)
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

2. upper_bound

在nums中查找第一个大于target的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
func upper_bound(nums []int, target int) int {
	l := 0
	r := len(nums)
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] <= target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}