二分查找算法刷题记录 -LC34

前言

接上文，本文记录LC34 排序数组中查找元素的第一个和最后一个位置题解。

该题是基于LC704的拓展题，也是二分查找的各个细节点所在，做透这个题，二分查找的题基本上都可以解决。

正文

在做本题前，请确保你已经掌握了二分查询的基础解法，并且能理解右指针开区间和闭区间两种解法的差异。题解如下

func searchRange(nums []int, target int) []int {
    return []int{searchLeft(nums,target),searchRight(nums,target)}
}

func searchRight(nums []int, target int) int {
    l,r := 0,len(nums)
    for l<r  {
        mid := l + (r-l)>>1
        if nums[mid]>target {
            r=mid
        }else if nums[mid]<target{
            l=mid+1
        }else{
            l=mid+1
        }
    }
    t := l - 1
    if t<0 || t>= len(nums) {
        return -1
    }
    if nums[t]!=target {
        return -1
    }
    return t
}
func searchLeft(nums []int, target int) int {
    l,r := 0,len(nums)
    for l<r  {
        mid := l + (r-l)>>1
        if nums[mid]>target {
            r = mid
        }else if nums[mid]<target{
            l=mid+1
        }else{
            r = mid 
        }
    }
    if l<0 || l >= len(nums) {
        return -1 
    }
    if nums[l] != target {
        return -1 
    }
    return l
    
}

这道题我认为首先要分为两部分来解：

实现找左边界函数和找右边界函数，由于左指针从0开始，右指针从len(nums)开始，实现方式是左闭右开的方式，这两个函数的实现在细节上是不一样的。

（1）找左边界函数searchLeft

首先左右指针的初始化、代码里的位运算等前文讲过了，就不过多介绍了。

重点来看在不同情况下l和r指针如何移动：

1.nums[mid]>target，说明在[left,right]中间位置mid index所取的值比target大，因此下一步寻找应该去[left,mid)找target所在的index，所以移动右指针 r=mid

2.nums[mid]<target，同理，下一步应该去[mid+1,right)找，因此移动左指针l=mid+1

3.nums[mid]==target时，如果是LC704，此时我们已经找到答案可以return，但是这里我们要找左边界，所以此时应该尽量将右指针往左移动，显然我们的结果应该在[left,mid]之间，也就是[left,mid+1）之间，但是mid这个位置在本次循环里已经查找过了，需要进一步缩小范围到[left,mid)，因此移动右指针r=mid

上面写完关键部分的逻辑后，还需要关注返回之前需要做的判断。

返回时有两种情况：

1.循环退出了，但是没有找到值为target的index。注意：

>>循环退出的条件是l=r，那么此时首先要判断l是否数组越界，即使 l<0 || l>=len(nums)，越界则 return -1。

>>如果没越界，那么判断l是不是target对应的索引？nums[l]==target?不成立则return -1。

>>如果nums[l]==target，说明确实找到了，return l。

（2）实现找右边界函数