【二分查找】704 二分查找

纠结的点

1. 二分左右边界下标得到的游标是否能被整除
   解决办法：与其分开被整除和不能被整除，不如就暂定游标cursor为向下取整。
   

正确解法（参考官方题解）

时间复杂度：O(logN)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return -1

        left = 0  # 数组下标左边界
        right = len(nums) - 1  # 数组下标右边界
        ret = -1

        while left <= right:
            # cursor 都是向下取整，避开分别判断是否要整除的问题
            cursor = left + (right - left) // 2
            if nums[cursor] == target:
                ret = cursor
                break
            if nums[cursor] < target:
                left = cursor + 1
            else:
                right = cursor - 1        
        return ret  

进阶题目：35. 搜索插入位置

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return 0
        
        # 初始化边界
        left = 0
        right = len(nums) - 1
        ret = -1

        while left <= right:
            cursor = left + (right - left) // 2
            if nums[cursor] == target:
                ret = cursor
                break
            elif nums[cursor] < target:
                left = cursor + 1
            else:
                right = cursor - 1
        
        # 判断是否数组中没有该元素
        if ret == -1 and right < left:
            ret = min(left, right) + 1

        return ret