二分模板

---

• nums数组默认从小到大排列

计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

左边界 [) 和 [] 两个模板（都把left作为解）

• 【） 模板

有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话老的二分算法是无法处理的。

本函数返回左端点的位置，如果超出数组位置（target<min(nums)）返回-1

完整代码：nums 数组默认有序，left，right对应范围[)，当left+1==right时或者left==right时确定唯一解。通过判定单边解得到只含双边解的情况[left,mid,right)，

def left_bound(nums, target) :
    # 单侧的情况直接返回解
    if target>nums[-1]:
        return len(nums)-1
    if target<nums[0]:
        return -1
    left=0
    right=len(nums)
    # [0,len(nums))
    while(left<right):
        mid=(left+right)//2
        if nums[mid]==target:
            right=mid
        elif nums[mid]<target:
            left=mid+1
            # 留下了target = 2 nums[left]=3的bug需要return前擦屁股
        elif nums[mid]>target:
            right=mid
    # 检查越界
    if nums[left]>target:
        left-=1
    return left

• 是否要越界检查得根据具体情况分析

• 【】模板

我个人还是喜欢[]的模板

def left_bound(nums, target) :
    # 单侧的情况直接返回解
    if target>nums[-1]:
        return len(nums)-1
    if target<nums[0]:
        return -1
    left=0
    right=len(nums)-1
    # [0,len(nums)-1]
    while(left<=right):
        print(left,right)
        mid=(left+right)//2
        if nums[mid]>=target:
            right=mid-1
            # mid 不可能是解，所以并没有right在该情况下没有问题
        elif nums[mid]<target:
            left=mid+1
            # 留下了target = 2 nums[left]=3所以退出while，
            # 需要return前擦屁股
    # 检查越界
    if nums[left]>target:
        left-=1
    return left

右边界

• [] 版

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