704. Binary Search

https://leetcode.com/problems/binary-search/

solution

• 左闭右闭

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1  # 闭区间

        while l <= r:  # 可能相等
            mid = l + (r - l) // 2
            if nums[mid] > target:
                r = mid - 1  # right - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid  # 输出mid
        return -1      

时间复杂度：O(logn) 空间复杂度：O(1)

• 左闭右开

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)  # 右开区间，需要右边界大于数组边界

        while l < r:  # 闭区间，则等于没有意义了
            mid = l + (r - l) // 2
            if nums[mid] > target:
                r = mid  # 闭区间，右边界本身就不在查找范围，因此mid不等于target也不在区间内
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid  # 输出mid
        return -1       

• 左闭右开-lower bound

class Solution:
    def lower_bound(self, nums, target):
        # find in range [left, right)
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:  # 即使相等, 右边也shrink
                right = mid
        return left  # 输出left

• 左闭右开-higher bound

class Solution:
    def higher_bound(self, nums, target):
        # find in range [left, right)
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:  # 即使相等，左边也shrink
                left = mid + 1
            else:
                right = mid
        return left  # 输出left

follow up

35. Search Insert Position

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return l  # 相比704, 主要考察输出

74. Search a 2D Matrix

*702. Search in a Sorted Array of Unknown Size

# 运用前提条件: [-9999, 9999]