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

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

通过次数103,884 | 提交次数261,002

Third Try

2020-07-02

第一眼看到这题以为很简单，但是写起来才发现自己并不会用二分法来查找左边界和右边界。最容易的解法是先用普通二分法查找一个数值，然后沿左右拓展，但如果所有数值一样这复杂度就超标了。

系统学习了一下通过二分法找左边界和右边界的方法，终于能够写出自己的版本了。只是看题解的话，还是很容易就被缩略合并的代码绕晕了。

左边界和右边界的关键在于当遇到nums[mid] == target时候的行为，其他内容完全一样。

对于左边界，我的思路是当遇到num[mid] == target的时候，直接默认right = mid - 1。由于新的[left, right]中的元素不会出现大于target的情况，这样的后果是right守住了最靠近target的位置。如果target只存在一次，那么在接下来的[left, right]中搜索的后果是变成了[right + 1, right]，亦即right一直都不会被改变。如果target存在多次，那么每次遇到相同的target只会导致right = mid - 1。最后的终结条件是left <= right被破坏，也即left = right + 1，但是其实并不需要去关注left的情况。循环结束后，需要判断target是否曾经出现过，right是否从mid - 1而来，因此只要判断nums[right + 1]是否等于target即可。如果target本来就比所有元素都大，结果是right并没有变化，还是等于len(nums) - 1, 直接判断nums[right + 1]会导致溢出，因此需要额外判断right + 1 < len(nums).

对于右边界，与左边界反着来就行了，也就是把left不断右移，最后判断left - 1是否符合条件即可。

有些题解里面判断终结条件是while left < right, 这时在普通二分法中处理遇到mid比target大的情况时，right是变成mid,而不是mid - 1；而left在遇到mid < target的时候仍然是left = mid + 1。这是因为right边界是开区间，并不会被使用。同时在这种情况下，初始条件left = 0，但是right = len(nums)而不是len(nums)-1.

对我而言，还是更习惯使用双开区间，也即while left <= right，在遇到mid的不同情况下，分别使用left = mid + 1和right = mid - 1.

不上左右边界之后，对于二分法算是终于补上漏洞了。之前觉得对二分法已经非常熟悉了，结果还是没想到一个简单的变形就不会了。

# 搞个标准的二分法查找左右边界
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 找左侧，靠右移；找 右侧，靠左移，真是神奇的思路
        def search_left(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] > target:
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                elif nums[mid] == target:
                    # 右边遇到相等的情况，往左边移动一位，移动后不一定还是target，也可能比target小
                    # 从此之后，target只可能大于等于下一轮的最大值，因此下一轮必然target >= nums[mid]
                    # 因此nums[mid] > target导致right = mid - 1的情况不会再出现了，要么是left + 1,要么是相等继续right = mid - 1
                    # 最后依然要判断是否这个right在移动前等于target,因此判断是right + 1
                    right = mid - 1
            # print('left', left, right, mid)
            if right + 1 < len(nums) and nums[right + 1] == target:
                return right + 1
            return -1

        def search_right(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] > target:
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                elif nums[mid] == target:
                    left = mid + 1
            # print("right", left, right, mid)
            if left - 1 >= 0 and nums[left - 1] == target:
                return left - 1
            return -1
        
        left = search_left(nums, target)
        if left == -1:
            return [-1, -1]

        rv = [left, search_right(nums, target)]
        # print(rv)
        return rv
                

执行用时：20 ms, 在所有 Python 提交中击败了79.02%的用户
内存消耗：13.3 MB, 在所有 Python 提交中击败了8.33%

Second Try

2020-07-02

先用普通方法查找一个点，然后向左向右延伸，问题仅仅在于如果整个表都是target，复杂度就变成了O(n)

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 随便找到一个，然后往左右拓展。勉强算是O(lgn + m)的算法吧，m是target中重复元素的数量
        if not len(nums):
            return [-1, -1]
        shoot = -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                shoot = mid
                break
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        if shoot == -1:
            return [-1, -1]
        left = right = shoot
        # 边界不注意又浪费了一次上传
        while left - 1 >= 0 and nums[left - 1] == target:  
            left -= 1
        while right + 1 < len(nums) and nums[right + 1] == target:
            right += 1
        return [left, right]

执行用时：20 ms, 在所有 Python 提交中击败了79.02%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了8.33%的用户

First Try

2020-07-02

一个比较傻逼的方法，使用二分法找到所有的target，复杂度是(m*logn)，还不如一遍线性查找。

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 看起来就是一个普通的二分法？细节得在写的过程中再思考了
        # 这个算法相当于用二分法找出所有的元素，不太行啊，还不如先找出第一个元素，然后往左往右拓展看看
        rv = []
        if not len(nums):
            return [-1, -1]       
        def div_search(nums, left, right, target, rv):
            if left > right:
                return -1
            mid = (left + right) // 2
            if nums[mid] == target:
                rv.append(mid)
                div_search(nums, left, mid - 1, target, rv)
                div_search(nums, mid + 1, right, target, rv)
            if nums[mid] < target:
                div_search(nums, mid + 1, right, target, rv)
            else:
                div_search(nums, left, mid - 1, target, rv)
        div_search(nums, 0, len(nums)-1, target, rv)
        # print(rv)
        rv  = sorted(rv)
        return [rv[0], rv[-1]] if len(rv) else [-1, -1]

执行用时：268 ms, 在所有 Python 提交中击败了5.28%的用户
内存消耗：29.1 MB, 在所有 Python 提交中击败了8.33%的用户