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

二分法的功能

• 查找某个元素的位置
• 查找某个元素的起始位置和末位置 to put it anthoer way 可以找到比该元素小或者比该元素大的元素的位置 进而可以找到该元素

python的三元表达式
item if condition else item

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 三种情况 二分查找也可以定位元素位置
        '''
        1 元素在数组的左边或者右边 但不属于数组
        2 元素在数组里面
        3 元素在数组范围内 但不在数组里面
        '''
        def get_right(nums,target):
            _riht = -2 # 标记情况1，元素在数组最左边
            left,right = 0,len(nums)-1 # 左闭右闭
            while left <= right:
                middle = (left + right) // 2
                if nums[middle] > target:
                    right = middle - 1
                else: # 包括小于或者等于的情况
                    left = middle + 1
                    _riht = left
            return _riht 
        def get_left(nums,target):
            _left = -2 # 标记情况1，元素在数组最左边
            left,right = 0,len(nums)-1 # 左闭右闭
            while left <= right:
                middle = (left + right) // 2
                if nums[middle] >= target:
                    right = middle - 1
                    _left = right
                else: # 包括大于或者等于的情况
                    left = middle + 1
            return  _left 

        right = get_right(nums,target)
        left = get_left(nums,target)
            
        # 情况一right
        if right == -2 or left == -2:
            return [-1,-1]
        # 情况二
        if  (right - left)> 1:
            return [left+1,right-1]
        # 情况三
        return [-1,-1]


```- 
刷题过程中注意分类讨论


```python
有一个有序数组nums和一个target
如果这个数在数组里面，那么返回第一个比这个数大的数
如果这个数不在数组里面，那么返回-1
'''

def solution(nums,target):
    left,right = 0,len(nums)-1
    r = -2
    while left <= right:
        middle= (left + right)//2
        if nums[middle] > target:
            right = middle - 1
        else:
            left = middle + 1
            r = left
    return r

def solution2(nums,target):
    left,right = 0,len(nums)-1
    r = -2
    while left <= right:
        middle= (left + right)//2
        if nums[middle] >= target:
            right = middle - 1
            r = right
        else:
            left = middle + 1 
    return r
r  = solution([1,2,3,4,5,6],5)
l = solution2([1,2,3,4,5,6],5)
print(r)
# 元素不在数组里面
if r == -2 or l == -2:
    print( -1 )
# 元素在里面
if (r - l) > 1:
    print(  [1,2,3,4,5,6][r-1] if r<len([1,2,3,4,5,6]) else -1)
print( -1 )