Week 11 @ 2025 算法周记【二分搜索】
By Bryan
In progress
3 min
二分搜索
LC 240. Search a 2D Matrix II 搜索二维矩阵 II
https://leetcode.com/problems/search-a-2d-matrix-ii/
（不是二分）
func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := 0, n-1
for i < m && j >= 0 {
v := matrix[i][j]
if v == target {
return true
}
if v < target {
i++
} else {
j--
}
}
return false
}LC 392. Is Subsequence 判断子序列
https://leetcode.com/problems/is-subsequence/description/
（不是二分）
func isSubsequence(s string, t string) bool {
if s == "" {
return true
}
j := 0
for i := 0; i < len(t); i++ {
if t[i] == s[j] {
j++
if j == len(s) {
return true
}
}
}
return false
}LC 792. Number of Matching Subsequences 匹配子序列的单词数
https://leetcode.com/problems/number-of-matching-subsequences/description/
暴力（没有超时）
func numMatchingSubseq(s string, words []string) int {
count := 0
for _, word := range words {
if isSubsequence(word, s) {
count++
}
}
return count
}
func isSubsequence(s string, t string) bool {
if s == "" {
return true
}
j := 0
for i := 0; i < len(t); i++ {
if t[i] == s[j] {
j++
if j == len(s) {
return true
}
}
}
return false
}预处理 + 二分
func numMatchingSubseq(s string, words []string) int {
chars := getCharIndexes(s)
count := 0
for _, word := range words {
if isSubsequence(chars, word) {
count++
}
}
return count
}
func getCharIndexes(s string) [][]int {
result := make([][]int, 26)
for i := range s {
idx := charToIdx(s[i])
result[idx] = append(result[idx], i)
}
return result
}
func charToIdx(c byte) int {
return int(c - 'a')
}
func isSubsequence(s [][]int, word string) bool {
j := -1
for i := 0; i < len(word); i++ {
j = search(s[charToIdx(word[i])], j)
if j == -1 {
return false
}
}
return true
}
func search(arr []int, prevIndex int) int {
target := prevIndex + 1
L, R := 0, len(arr)-1
for L < R {
mid := L + (R - L) / 2
if arr[mid] >= target {
R = mid
} else {
L = mid + 1
}
}
if R < 0 || R >= len(arr) {
return -1
}
if arr[R] <= prevIndex {
return -1
}
return arr[R]
}LC 658. 找到 K 个最接近的元素
https://leetcode.com/problems/find-k-closest-elements/description/
func findClosestElements(arr []int, k int, x int) []int {
ii := leftBound(arr, x)
if ii == len(arr) {
return arr[len(arr)-k:len(arr)]
}
result := make([]int, 0, k)
i, j := ii-1, ii // a < b
for len(result) < k {
if i < 0 {
result = append(result, arr[j:j+k-len(result)]...)
break
}
if j >= len(arr) {
result = append(result, arr[i+1-k+len(result):i+1]...,
)
break
}
if x-arr[i] <= arr[j]-x {
result = append(result, arr[i])
i--
} else {
result = append(result, arr[j])
j++
}
}
sort.Ints(result)
return result
}
func leftBound(arr []int, x int) int {
L, R := 0, len(arr)
for L < R {
mid := L + (R - L) / 2
if arr[mid] >= x {
R = mid
} else {
L = mid + 1
}
}
return R
}LC 35. Search Insert Position 搜索插入位置
https://leetcode.com/problems/search-insert-position/description/
func searchInsert(nums []int, target int) int {
L, R := 0, len(nums)
for L < R {
mid := L + (R - L) / 2
if nums[mid] >= target {
R = mid
} else {
L = mid + 1
}
}
return R
}LC 162. Find Peak Element 寻找峰值
https://leetcode.com/problems/find-peak-element/description/
func findPeakElement(nums []int) int {
L, R := 0, len(nums)
for L < R {
mid := L + (R -L) / 2
if mid == len(nums)-1 || nums[mid] > nums[mid + 1] {
R = mid
} else {
L = mid + 1
}
}
return R
}, multiple selections available,