算法42--Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

给定一个升序数组，求出某个元素在数组中的起始位置

利用二分查找，lo  hi  mid三个指针

当nums[mid]==target时，依次向左右两边寻找，直至数组边界或者某个位置值不等于target为止。

例如nums=[1,2,3,,3,3,3,3,3,3,3,3,3,4,5,6]  target=3 当nums[mid]==3时，需要向左右两边遍历直到某个值不等于3或者已经到达数组边界为止。

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lo = 0
        hi = len(nums)-1
        start = -1
        end = -1
        while lo<=hi:
            mid = (lo+hi)>>1
            if nums[mid]==target:
                start = mid
                end = mid
                while start>=1 and nums[start]==nums[start-1]:                   
                    start -= 1
                while end<len(nums)-1 and nums[end]==nums[end+1]:                    
                    end += 1
                return start, end
            elif nums[mid]>target:
                hi = mid-1
            else:
                lo = mid+1
        return start, end

别人的解法：

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1, -1]

        def bisect_left(nums, target):
            l, r = 0, len(nums) - 1
            while l < r:
                m = (l + r) // 2
                if nums[m] < target:
                    l = m + 1
                else:
                    r = m
            return l if nums[l] == target else -1

        def bisect_right(nums, target):
            l, r = 0, len(nums) - 1
            while l < r:
                m = (l + r) // 2 + 1
                if nums[m] > target:
                    r = m - 1
                else:
                    l = m
            return l if nums[l] == target else -1

        return [bisect_left(nums, target), bisect_right(nums, target)]