数据结构与算法-二分查找

常见二分查找模板与分类

🔁 模板一：标准二分查找

精确查找等于目标值



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



left, right := 0, len(nums)-1

for left <= right {
	mid := left + (right-left)/2
	if nums[mid] == target {
		return mid
	} else if nums[mid] < target {
		left = mid + 1
	} else {
		right = mid - 1
	}
}
return -1

704. 二分查找 



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



func search(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for left <= right {
        mid := left +(right - left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

367. 有效的完全平方数 



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



func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
    left, right := 1, num/2
    for left <= right {
        mid := left +(right-left)/2
        if mid*mid==num {
            return true
        } else if mid * mid > num {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return false
}

🔁 模板二：二分查找下界问题

查找左边界，查找大于等于给定值的第一个元素



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



left, right := 0, len(nums)-1
res := -1

for left <= right {
	mid := left + (right-left)/2
	if nums[mid] >= target {
		res = mid
		right = mid - 1
	} else {
		left = mid + 1
	}
}
return res

34. 在排序数组中查找元素的第一个和最后一个位置 



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



func searchRange(nums []int, target int) []int {
	left := findLeft(nums, target)
	right := findRight(nums, target)
	return []int{left, right}
}

// 找左边界（第一个等于 target 的位置）
func findLeft(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] == target {
			res = mid
			right = mid - 1
		}
	}
	return res
}

// 找右边界（最后一个等于 target 的位置）
func findRight(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] == target {
			res = mid
			left = mid + 1
		}
	}
	return res
}

35. 搜索插入位置 



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



func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

278. 第一个错误的版本 



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



func firstBadVersion(n int) int {
	left, right := 1, n
	var res int
	for left <= right {
		mid := left + (right-left)/2
		if isBadVersion(mid) {
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

744. 寻找比目标字母大的最小字母 



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



func nextGreatestLetter(letters []byte, target byte) byte {
	left, right := 0, len(letters)-1
	for left <= right {
		mid := left + (right-left)/2
		if letters[mid] <= target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if left == len(letters) {
		return letters[0]
	}
	return letters[left]
}

1060. 有序数组中的缺失元素

image-20221111111120876



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



func missingElement(nums []int, k int) int {
	// 表示到第 i 个位置缺失了多少个数
	miss := func(i int) int {
		return nums[i] - nums[0] - i
	}

	left, right := 0, len(nums)-1
	for left <= right {
		mid := (left + right) / 2
		if miss(mid) < k {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return nums[left-1] + k - miss(left-1)
}

🔁 模板三：二分查找上界问题

查找有边界，查找小于等于给定值的最后一个元素



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



left, right := 0, len(nums)-1
res := -1

for left <= right {
	mid := left + (right-left)/2
	if nums[mid] <= target {
		res = mid
		left = mid + 1
	} else {
		right = mid - 1
	}
}
return res

34. 在排序数组中查找元素的第一个和最后一个位置 



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



func searchRange(nums []int, target int) []int {
	left := findLeft(nums, target)
	right := findRight(nums, target)
	return []int{left, right}
}

// 找左边界（第一个等于 target 的位置）
func findLeft(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] == target {
			res = mid
			right = mid - 1
		}
	}
	return res
}

// 找右边界（最后一个等于 target 的位置）
func findRight(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] == target {
			res = mid
			left = mid + 1
		}
	}
	return res
}

69. x 的平方根

sqrt(x) x 的平方根



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



func mySqrt(x int) int {
	if x == 0 {
		return 0
	}
	left, right := 1, x
    var res int
	for left <= right {
		mid := left + (right-left)/2
		if mid <= x/mid {
            res = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return res
}

441. 排列硬币

我们要找最大的 k，使得前 k 行的硬币数之和不超过 n：1 + 2 + 3 + … + k = k * (k + 1) / 2 <= n

所以题目可以转化为：给定 n，求满足 k(k+1)/2 ≤ n 的最大整数 k。



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



func arrangeCoins(n int) int {
    left, right := 0, n
    for left <= right {
        mid := (left + right) / 2
        sum := mid * (mid + 1) / 2
        if sum == n {
            return mid
        } else if sum < n {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

🔁 模板四：旋转排序数组二分查找

有序数组被部分旋转，例如：nums 原本有序，后来被旋转，例如 [4,5,6,7,0,1,2]



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



left, right := 0, len(nums)-1

for left <= right {
	mid := left + (right-left)/2
	if nums[mid] == target {
		return mid
	}

	if nums[left] <= nums[mid] {
		// 左边有序
		if nums[left] <= target && target < nums[mid] {
			right = mid - 1
		} else {
			left = mid + 1
		}
	} else {
		// 右边有序
		if nums[mid] < target && target <= nums[right] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
}
return -1

33. 搜索旋转排序数组

image-20210102184623651



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



func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}

		if nums[mid] > nums[right] {
			if target >= nums[left] && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else if nums[mid] < nums[right] {
			if target > nums[mid] && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		} else {
			right--
		}
	}
	return -1
}

81. 搜索旋转排序数组 II 



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



func search(nums []int, target int) bool {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return true
		}
		if nums[mid] > nums[right] {
			// 左半部分有序
			if target >= nums[left] && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else if nums[mid] < nums[right] {
			// 右半部分有序
			if target > nums[mid] && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		} else {
			right--
		}
	}
	return false
}

153. 寻找旋转排序数组中的最小值 



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



func findMin(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] > nums[right] {
			left = mid + 1
		} else if nums[mid] < nums[right] {
			right = mid
		} else {
			right--
		}
	}
	return nums[left]
}

154. 寻找旋转排序数组中的最小值 II 



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



func findMin(nums []int) int {
	left, right := 0, len(nums)-1

	for left < right {
		mid := left + (right-left)/2

		// 如果中间值大于右边值，最小值在右边
		if nums[mid] > nums[right] {
			left = mid + 1
		} else if nums[mid] < nums[right] {
			right = mid
		} else { // nums[mid] == nums[right] 时不能确定，缩小右边界
			right--
		}
	}

	return nums[left]
}

剑指 Offer 11. 旋转数组的最小数字 



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



func inventoryManagement(nums []int) int {
    left, right := 0, len(nums) - 1
    for left < right {
        mid := left + (right - left) / 2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

面试题 10.03. 搜索旋转数组 



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



func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1
	for left <= right {
		if nums[left] == target {
			return left
		}
		mid := left + (right-left)/2
		if nums[mid] == target {
			res = mid
			right = mid - 1
		} else if nums[mid] > nums[right] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else if nums[mid] < nums[right] {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		} else {
			right--
		}
	}
	return res
}

🔁 模板五：二维矩阵二分查找

74. 搜索二维矩阵 



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



func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}

	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1

	for left <= right {
		mid := left + (right-left)/2
		row := mid / n // 计算对应的行
		col := mid % n // 计算对应的列

		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return false
}

378. 有序矩阵中第 K 小的元素 



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



func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    left, right := matrix[0][0], matrix[n-1][n-1]

    for left < right {
        mid := left + (right-left)/2
        count := 0
        j := n - 1

        for i := 0; i < n; i++ {
            for j >= 0 && matrix[i][j] > mid {
                j--
            }
            count += j + 1
        }

        if count < k {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return left
}

🔁 模板六：峰值二分

寻找数组中的最小值/峰值



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



left, right := 0, len(nums)-1
for left < right {
	mid := left + (right-left)/2
	if nums[mid] > nums[mid+1] {
		// 局部递减，峰值在左侧（含 mid）
		right = mid
	} else {
		// 局部递增，峰值在右侧
		left = mid + 1
	}
}
return left

162. 寻找峰值 



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



func findPeakElement(nums []int) int {
	left, right := 0, len(nums)-1

	for left < right {
		mid := (left + right) / 2
		// 如果中间比右边小，说明右边有峰值
		if nums[mid] < nums[mid+1] {
			left = mid + 1
		} else {
			// 否则左边有峰值，或 mid 自己就是峰值
			right = mid
		}
	}

	// 最终 left == right，返回任意一个峰值下标
	return left
}

852. 山脉数组的峰顶索引 



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



func peakIndexInMountainArray(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] > nums[mid+1] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

1095. 山脉数组中查找目标值 



1



write your code here

其他经典题

百度面试题-有序数组中绝对值最小的元素

image-20250420221452672



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



func findMinAbs(nums []int) int {
	n := len(nums)
	if nums[0] >= 0 {
		return nums[0] // 所有元素非负，最小绝对值为第一个
	}
	if nums[n-1] <= 0 {
		return nums[n-1] // 所有元素非正，最小绝对值为最后一个
	}

	left, right := 0, n-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == 0 {
			return 0 // 绝对值最小就是 0
		} else if nums[mid] < 0 {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	// 此时 left 指向第一个正数，right 指向最后一个负数
	if abs(nums[left]) < abs(nums[right]) {
		return nums[left]
	}
	return nums[right]
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

540. 有序数组中的单一元素 



1
2
3
4
5
6
7



func singleNonDuplicate(nums []int) int {
	res := 0
	for _, num := range nums {
		res ^= num
	}
	return res
}
本文作者:
本文链接: https://hgnulb.github.io/blog/2020/94980842
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！