題目鏈接
難度：中等 ??????類型： 二分搜索

給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置。

你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。

如果數(shù)組中不存在目標(biāo)值，返回 [-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]

解題思路

用兩次二分搜索，一次找左邊界，一次找右邊界
找兩個(gè)邊界的方式不太一樣
找左邊界時(shí)，若nums[mid]==target，要移動(dòng)右指針
找右邊界時(shí)，若nums[mid]==target，要移動(dòng)左指針

找右邊界時(shí)，左指針直接指向左邊界會(huì)減小搜索范圍

代碼實(shí)現(xiàn)

class Solution(object):
    def search_border(self, nums, target, l, is_left):
        r = len(nums)
        while l<r:
            mid = (l+r)//2
            if nums[mid]>target or (is_left and target==nums[mid]):
                r = mid
            else:
                l = mid + 1 
        return l
    
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = self.search_border(nums, target, 0, True)
        if left==len(nums) or nums[left]!=target:
            return [-1,-1]      
        right = self.search_border(nums, target, left, False) - 1  
        return [left, right]

本文鏈接：http://www.itdecent.cn/p/16f1677f2e03