LC34. Find First and Last Position of Element in Sorted Array

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

This is a simple application of binary search. The hard is part is how to tweak binary search to return the first (or last) index of a given target.

We do binary search as normal, and compare nums[mid] and target. If they are equal, we can’t just return mid, because this might be any of the targets in the array; we also can’t let high = mid or low = mid and keep searching, because it is possible that low and high will never meet in this case. Therefore, we must manually check if nums[mid] is the first (or last) target in the array. If so, just return mid; otherwise, let high = mid - 1 or low = mid + 1 and keep searching.

这是一道二分查找的简单应用题，难点在于查找某个元素的第一个和最后一个下标。

我们正常进行二分查找，比较 nums[mid] 与 target。如果它们相等，我们不能直接返回，因为返回的可能是任意一个 target。那我们可以直接令 high = mid 或者 low = mid 继续查找吗？也不可以，因为这样会造成 low 和 high 永远无法相遇。所以必须在此时检查 nums[mid] 是否是第一个（最后一个）target。如果是的话直接返回 mid，否则才令 high = mid - 1 或者 low = mid + 1 继续查找。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch(nums, target, low, high, first):
            while low < high:
                # print(low, high)
                mid = (low + high) // 2
                if first:
                    if nums[mid] == target and \
                            (mid == 0 or nums[mid-1] < target):
                        return mid
                    elif nums[mid] >= target:
                        high = mid - 1
                    else:
                        low = mid + 1
                else:
                    if nums[mid] == target and \
                            (mid == len(nums)-1 or nums[mid+1] > target):
                        return mid
                    elif nums[mid] <= target:
                        low = mid + 1
                    else:
                        high = mid - 1
            if low == high and nums[low] == target:
                return low
            else:
                return -1
        l = binarySearch(nums, target, 0, len(nums)-1, True)
        r = binarySearch(nums, target, 0, len(nums)-1, False)
        return [l, r]