死磕二分

致敬经典二分

每一个细节都有它的道理：

• left <= right 允许等于的情况
  • 因为当区间只含有一个元素时 程序可以handle
    • 这个元素等于target直接return
    • 不等于 区间收缩 可以跳出循环体
• 循环体内对target判断的必要性
  • 提高程序效率 可能提前就找到target
  • 为了每一轮循环区间都可以得到收缩

def binarySearch(self, nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid + 1
        elif nums[mid] < target:  
            left = mid + 1
        else:
            right = mid - 1
    return -1

衍生问题

nums有重复元素，查找target，如果有多个元素，返回最左边元素的index，如果target不存在，返回target需要插入的index（插入之后nums依然有序）

基于经典二分改写

整体框架和经典二分一样，每一轮循环对重复元素左端点进行判断，有可能直接找到左端点，直接return

def bs_duplicate(self, nums, target):
    left, right = 0, len(nums) - 1
    while left <= right: # 能保证区间一直收缩，
        mid = left + (right - left) // 2
        if nums[mid] == target:
            if mid >= 1 and nums[mid - 1] == target:
                right = mid - 1
            else:
                return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left

不一样的写法

不同于经典二分的地方：

• while循环 条件 没有等于号
  • 当区间大小变成1的时候 避免死循环的出现
• 不做检查 对于nums[mid] ==target的情况 采用保留mid这个index的方法

def binarySearch2(self, nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target: # target 位于右半段
            left = mid + 1
        else: # num[mid] <= target
            right = mid # 因为nums[mid] == target 是可能的 所以mid这个位置不能丢
    # return right if nums[right] == target else -1
    return right

容易出现的错误

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

可以测试，上面的代码对于nums=[0,2], target=1的情况直接死循环

因为在做区间收缩之前就有left == mid，区间收缩直接失效 陷入死循环

根本原因在于mid的计算是偏向左边的，mid = (left + right) // 2， 对于case [0,2] left= mid=0, right=1

所以在写区间收缩的代码时候需要警惕left = mid的情况。

旋转数组最小值 （无重复元素）

left < right ==> mid < right 因为mid可能等于left但是绝对不可能等于right 前提是数组元素个数大于1
nums[mid] != nums[right]
所以可以比较nums[mid] 和 nums[right] 并且只有两种情况
nums[mid] > nums[right] 说明最小值在右半段 可以推出nums[mid]不可能是最小值 所以可以放心的让 left = mid + 1
nums[mid] < nums[right] 说明最小值在左半端 不能让right = mid - 1 因为mid可能是最小值 
        只能够是 right = mid 那么这样会不会使得区间不收缩 陷入死循环呢 答案是不会 因为 mid < right 区间必然收缩
当while的判断条件不再满足 left == right 找到最优解

class Solution_:
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid 
        return nums[left]

right = mid 这行代码只要数组元素个数大于1，都可以保证区间收缩