二分查找(Python实现)

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None


my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 7))
print(binary_search(my_list, -1))

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums: return 0
        left, right = 0, len(nums)-1
        while left + 1 < right:
            mid = (left + right) >> 1
            if nums[mid] < target:
                left = mid
            else:
                right = mid
        count, end = 0,len(nums)-1
        if nums[left] == target:
            while left <= end and nums[left] == target :
                left += 1
                count += 1
            return count
        elif nums[right] == target:
            while right <= end and nums[right] == target:
                right += 1
                count += 1
            return count
        else: return 0

class Solution:
   def searchRange(self, nums: List[int], target: int) -> List[int]:
       if not nums: return [-1, -1]
       # 确定左边界
       left, right = 0, len(nums)-1
       while left + 1 < right:
           mid = (left + right) >> 1
           if nums[mid] >= target: 
               right = mid 
           else: 
               left = mid 
       if nums[left] == target:    lbound = left
       elif nums[right] == target: lbound = right
       else: return [-1, -1]
       # 确定右边界
       left, right = 0, len(nums)-1
       while left + 1 < right:
           mid = (left + right) >> 1
           if nums[mid] <= target: 
               left = mid
           else: 
               right = mid 
       if nums[right] == target:  rbound = right
       elif nums[left] == target: rbound = left
       else: return [-1,-1]

       return [lbound, rbound]