LeetCode 二分查找问题

二分查找我觉得是个我特别容易出错的方法，我至少自己笔记都写过很多次，但是每次刷题还是会忘了细节，所以再推一次石头，再写一篇笔记

从性质的角度来理解二分

如果一个数组可以被某个性质分成两部分，其中一部分符合这个性质，另一部分不符合这个性质，则这个数组是可以二分的。以前很喜欢说的一个事情是如果数组单调则可以二分，但是我觉得可能这个更本质的，就是一个性质可以把数组严格分成两类，这其中当然可以有单调，但是也可以有其他性质。

进一步，我们思考这个性质，自然就分成了两类，第一种情况是数组的前半部分符合性质，第二种是数组的后半部分符合性质。而二分的目标也就对应划分成了以下两种：

在符合性质的后半段里，找到第一个符合性质的元素
在符合性质的前半段里，找到最后一个符合性质的元素

我是觉得从这个角度来理解二分还挺容易的，至少对我来说吧

对应的二分查找模板

性质为准，中心逆边，命中顺边，终点在左：先考虑我们要的性质在左边还是右边，对应的中心选取的时候要选择相逆的那一边（是向上取值还是向下取整），如果中心命中了性质则顺边的指标移动，循环结束以后左指针的位置就是我们要的答案

性质在前面

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


// 当性质P把数组分成 [TTTT|FFFF] 时使用
// 找最后一个满足性质P的位置
func bsearch2(l, r int) int {
    for l < r {
        mid := l + (r-l+1)/2  // 向上取整
        if P(mid) {
            // [TTTT|T]FFF
            //        ↑mid 可能是最后一个T
            l = mid           // 保留mid
        } else {
            // TTT[T|FFFF]
            //     ↑mid 一定不是最后一个T
            r = mid - 1       // 排除mid
        }
    }
    return l

性质在后面

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


// 当性质P把数组分成 [FFFF|TTTT] 时使用
// 找第一个满足性质P的位置
func bsearch1(l, r int) int {
    for l < r {
        mid := l + (r-l)/2    // 向下取整
        if P(mid) {
            // [FFFF|T]TTT
            //      ↑mid 可能是第一个T
            r = mid           // 保留mid
        } else {
            // FFFF[F|TTTT]
            //      ↑mid 一定不是第一个T
            l = mid + 1       // 排除mid
        }
    }
    return l
}

LC4 寻找两个正序数组的中位数

这题是真的难，最后实现的时候用的是二分，但是没有用我们的板子，它的核心是这样，定义一个函数，这个函数返回的是两个数组中第k小的元素，然后我们的中位数其实就是第(n+m)/2小的元素，所以我们可以二分这个k，然后找到这个k，然后返回

进一步，我们如何去实现这个函数呢？

我们先规定顺序，要求第一个数组剩余的长度要是小于第二个数组的，否则逆向
如果第一个数组搜完了，那第二个数组直接按序即可
如果k==1，那么我们只需要比较两个数组的第一个元素，然后返回较小的那个
如果k>1，那么我们就可以二分这个k，我们先往前走k/2步，然后比较两个数组中第k/2小的元素，如果第一个数组中的元素小，那么我们就排除第一个数组的前k/2个元素，否则就排除第二个数组的前k/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
26
27
28
29
30


func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    totalLen := len(nums1) + len(nums2)
    if totalLen % 2 == 1{
        return float64(findKth(nums1, nums2, 0, 0, totalLen / 2 + 1))
    }
    return float64(findKth(nums1, nums2, 0, 0, totalLen / 2) 
        + findKth(nums1, nums2, 0, 0, totalLen / 2 + 1)) / 2
}

// idx1, idx2 是两个数组的起始位置，包括
// k 是我们要找的第k小的元素，从1开始
func findKth(nums1, nums2 []int, idx1, idx2, k int) int{
    // 边界处理
    switch{
    case len(nums1) - idx1 > len(nums2) - idx2:
        return findKth(nums2, nums1, idx2, idx1, k)
    case len(nums1) == idx1:
        return nums2[idx2 + k - 1]
    case k == 1:
        return min(nums1[idx1], nums2[idx2])
    }
    // 计算新的索引
    nxt1 := min(len(nums1), idx1 + k / 2)
    nxt2 := min(len(nums2), idx2 + k / 2)
    // 返回
    if nums1[nxt1 - 1] < nums2[nxt2 - 1]{
        return findKth(nums1, nums2, nxt1, idx2, k - (nxt1 - idx1))
    }
    return findKth(nums1, nums2, idx1, nxt2, k - (nxt2 - idx2))
}

LC34 在排序数组中查找元素的首尾位置

这题就很有趣，它要求我们找到元素的第一个和最后一个位置，与此同时它给的数组是排序的，所以我们可以用二分来找到第一个位置和最后一个位置

找第一个匹配位置，就是找第一个大于等于target的元素，这里相当于是性质在后面
找最后一个匹配位置，就是找最后一个小于等于target的元素，这里相当于是性质在前面

 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


func searchRange(nums []int, target int) []int {
	
    res := []int{-1, -1}
    l, r := 0, len(nums)-1

    if r == -1{
        return res 
    }

    for l < r {
        mid := (l+r) / 2
        if nums[mid] >= target{
            r = mid 
        }else{
            l = mid + 1
        }
    }

    if nums[l] != target{
        return res 
    }else{
        res[0], r = l, len(nums) - 1 
    }

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

    res[1] = l
    return res
}