10/8 每日一題(使用二分法找出target的索引, 如果沒有救回傳-1)

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

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

You must write an algorithm with O(log n) runtime complexity.

 

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]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

 class Solution:

   

    def bin_search(self,nums,target,left_line):

        l=0

        r=len(nums)-1

        res=-1

        while l<=r:

            mid=(l+r)//2

            if nums[mid]==target:

                res=mid

                if left_line:

                    '繼續找左邊的'

                    r=mid-1

                else:

                    '繼續找右邊'

                    l=mid+1

            elif nums[mid]<target:

                l=mid + 1

            else:

                r = mid - 1

        return res    

   

    def searchRange(self, nums: List[int], target: int) -> List[int]:

        left = self.bin_search(nums,target,True)

        right= self.bin_search(nums,target,False)

        return [left,right]