二分搜索

二分搜索模板

给一个有序数组和目标值,找第一次/最后一次/任何一次出现的索引,如果没有出现返回-1
模板四点要素
  • 1、初始化:start=0、end=len-1
  • 2、循环退出条件:start + 1 < end
  • 3、比较中点和目标值:A[mid] ==、 <、> target
  • 4、判断最后两个元素是否符合:A[start]、A[end] ? target
时间复杂度 O(logn),使用场景一般是有序数组的查找
典型示例
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
1
// 二分搜索最常用模板
2
func search(nums []int, target int) int {
3
// 1、初始化start、end
4
start := 0
5
end := len(nums) - 1
6
// 2、处理for循环
7
for start+1 < end {
8
mid := start + (end-start)/2
9
// 3、比较a[mid]和target值
10
if nums[mid] == target {
11
end = mid
12
} else if nums[mid] < target {
13
start = mid
14
} else if nums[mid] > target {
15
end = mid
16
}
17
}
18
// 4、最后剩下两个元素,手动判断
19
if nums[start] == target {
20
return start
21
}
22
if nums[end] == target {
23
return end
24
}
25
return -1
26
}
Copied!
大部分二分查找类的题目都可以用这个模板,然后做一点特殊逻辑即可
另外二分查找还有一些其他模板如下图,大部分场景模板#3 都能解决问题,而且还能找第一次/最后一次出现的位置,应用更加广泛
binary_search_template
所以用模板#3 就对了,详细的对比可以这边文章介绍:二分搜索模板
如果是最简单的二分搜索,不需要找第一个、最后一个位置、或者是没有重复元素,可以使用模板#1,代码更简洁
1
// 无重复元素搜索时,更方便
2
func search(nums []int, target int) int {
3
start := 0
4
end := len(nums) - 1
5
for start <= end {
6
mid := start + (end-start)/2
7
if nums[mid] == target {
8
return mid
9
} else if nums[mid] < target {
10
start = mid+1
11
} else if nums[mid] > target {
12
end = mid-1
13
}
14
}
15
// 如果找不到,start 是第一个大于target的索引
16
// 如果在B+树结构里面二分搜索,可以return start
17
// 这样可以继续向子节点搜索,如:node:=node.Children[start]
18
return -1
19
}
Copied!

常见题目

给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。 如果目标值不在数组中,则返回[-1, -1]
思路:核心点就是找第一个 target 的索引,和最后一个 target 的索引,所以用两次二分搜索分别找第一次和最后一次的位置
1
func searchRange (A []int, target int) []int {
2
if len(A) == 0 {
3
return []int{-1, -1}
4
}
5
result := make([]int, 2)
6
start := 0
7
end := len(A) - 1
8
for start+1 < end {
9
mid := start + (end-start)/2
10
if A[mid] > target {
11
end = mid
12
} else if A[mid] < target {
13
start = mid
14
} else {
15
// 如果相等,应该继续向左找,就能找到第一个目标值的位置
16
end = mid
17
}
18
}
19
// 搜索左边的索引
20
if A[start] == target {
21
result[0] = start
22
} else if A[end] == target {
23
result[0] = end
24
} else {
25
result[0] = -1
26
result[1] = -1
27
return result
28
}
29
start = 0
30
end = len(A) - 1
31
for start+1 < end {
32
mid := start + (end-start)/2
33
if A[mid] > target {
34
end = mid
35
} else if A[mid] < target {
36
start = mid
37
} else {
38
// 如果相等,应该继续向右找,就能找到最后一个目标值的位置
39
start = mid
40
}
41
}
42
// 搜索右边的索引
43
if A[end] == target {
44
result[1] = end
45
} else if A[start] == target {
46
result[1] = start
47
} else {
48
result[0] = -1
49
result[1] = -1
50
return result
51
}
52
return result
53
}
Copied!
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
1
func searchInsert(nums []int, target int) int {
2
// 思路:找到第一个 >= target 的元素位置
3
start := 0
4
end := len(nums) - 1
5
for start+1 < end {
6
mid := start + (end-start)/2
7
if nums[mid] == target {
8
// 标记开始位置
9
start = mid
10
} else if nums[mid] > target {
11
end = mid
12
} else {
13
start = mid
14
}
15
}
16
if nums[start] >= target {
17
return start
18
} else if nums[end] >= target {
19
return end
20
} else if nums[end] < target { // 目标值比所有值都大
21
return end + 1
22
}
23
return 0
24
}
Copied!
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
1
func searchMatrix(matrix [][]int, target int) bool {
2
// 思路:将2纬数组转为1维数组 进行二分搜索
3
if len(matrix) == 0 || len(matrix[0]) == 0 {
4
return false
5
}
6
row := len(matrix)
7
col := len(matrix[0])
8
start := 0
9
end := row*col - 1
10
for start+1 < end {
11
mid := start + (end-start)/2
12
// 获取2纬数组对应值
13
val := matrix[mid/col][mid%col]
14
if val > target {
15
end = mid
16
} else if val < target {
17
start = mid
18
} else {
19
return true
20
}
21
}
22
if matrix[start/col][start%col] == target || matrix[end/col][end%col] == target{
23
return true
24
}
25
return false
26
}
Copied!
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
1
func firstBadVersion(n int) int {
2
// 思路:二分搜索
3
start := 0
4
end := n
5
for start+1 < end {
6
mid := start + (end - start)/2
7
if isBadVersion(mid) {
8
end = mid
9
} else if isBadVersion(mid) == false {
10
start = mid
11
}
12
}
13
if isBadVersion(start) {
14
return start
15
}
16
return end
17
}
Copied!
假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。
1
func findMin(nums []int) int {
2
// 思路:/ / 最后一个值作为target,然后往左移动,最后比较start、end的值
3
if len(nums) == 0 {
4
return -1
5
}
6
start := 0
7
end := len(nums) - 1
8
9
for start+1 < end {
10
mid := start + (end-start)/2
11
// 最后一个元素值为target
12
if nums[mid] <= nums[end] {
13
end = mid
14
} else {
15
start = mid
16
}
17
}
18
if nums[start] > nums[end] {
19
return nums[end]
20
}
21
return nums[start]
22
}
Copied!
假设按照升序排序的数组在预先未知的某个点上进行了旋转 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。(包含重复元素)
1
func findMin(nums []int) int {
2
// 思路:跳过重复元素,mid值和end值比较,分为两种情况进行处理
3
if len(nums) == 0 {
4
return -1
5
}
6
start := 0
7
end := len(nums) - 1
8
for start+1 < end {
9
// 去除重复元素
10
for start < end && nums[end] == nums[end-1] {
11
end--
12
}
13
for start < end && nums[start] == nums[start+1] {
14
start++
15
}
16
mid := start + (end-start)/2
17
// 中间元素和最后一个元素比较(判断中间点落在左边上升区,还是右边上升区)
18
if nums[mid] <= nums[end] {
19
end = mid
20
} else {
21
start = mid
22
}
23
}
24
if nums[start] > nums[end] {
25
return nums[end]
26
}
27
return nums[start]
28
}
Copied!
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。 你可以假设数组中不存在重复的元素。
1
func search(nums []int, target int) int {
2
// 思路:/ / 两条上升直线,四种情况判断
3
if len(nums) == 0 {
4
return -1
5
}
6
start := 0
7
end := len(nums) - 1
8
for start+1 < end {
9
mid := start + (end-start)/2
10
// 相等直接返回
11
if nums[mid] == target {
12
return mid
13
}
14
// 判断在那个区间,可能分为四种情况
15
if nums[start] < nums[mid] {
16
if nums[start] <= target && target <= nums[mid] {
17
end = mid
18
} else {
19
start = mid
20
}
21
} else if nums[end] > nums[mid] {
22
if nums[end] >= target && nums[mid] <= target {
23
start = mid
24
} else {
25
end = mid
26
}
27
}
28
}
29
if nums[start] == target {
30
return start
31
} else if nums[end] == target {
32
return end
33
}
34
return -1
35
}
Copied!
注意点
面试时,可以直接画图进行辅助说明,空讲很容易让大家都比较蒙圈
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。(包含重复元素)
1
func search(nums []int, target int) bool {
2
// 思路:/ / 两条上升直线,四种情况判断,并且处理重复数字
3
if len(nums) == 0 {
4
return false
5
}
6
start := 0
7
end := len(nums) - 1
8
for start+1 < end {
9
// 处理重复数字
10
for start < end && nums[start] == nums[start+1] {
11
start++
12
}
13
for start < end && nums[end] == nums[end-1] {
14
end--
15
}
16
mid := start + (end-start)/2
17
// 相等直接返回
18
if nums[mid] == target {
19
return true
20
}
21
// 判断在那个区间,可能分为四种情况
22
if nums[start] < nums[mid] {
23
if nums[start] <= target && target <= nums[mid] {
24
end = mid
25
} else {
26
start = mid
27
}
28
} else if nums[end] > nums[mid] {
29
if nums[end] >= target && nums[mid] <= target {
30
start = mid
31
} else {
32
end = mid
33
}
34
}
35
}
36
if nums[start] == target || nums[end] == target {
37
return true
38
}
39
return false
40
}
Copied!

总结

二分搜索核心四点要素(必背&理解)
  • 1、初始化:start=0、end=len-1
  • 2、循环退出条件:start + 1 < end
  • 3、比较中点和目标值:A[mid] ==、 <、> target
  • 4、判断最后两个元素是否符合:A[start]、A[end] ? target

练习题

最近更新 1yr ago