L2_二分查找

https://algorithm.yuanbin.me/zh-hans/basics_algorithm/binary_search.html

二分里等于的那个头，start或者end，后面后判断。因为等于了还被移动，答案就在另一半了。

binary search 模板
//first occurrence of target
int binarySearch(vector<int> &A, int target){
    if(A.size()==0){
        return -1;
    }
    int start=0;
    int end=A.size()-1;
    int mid;
    while(start+1<end){
        mid=start+（end-start）/2;
        if(A[mid]==target)
            end=mid;
        else if(A[mid]>target)
            end=mid; //不用mid+1之类
        else
            start=mid;
    }
//Mid不变，所以最后需要分别判断
    if(A[start]==target)
        return start;
    if(A[end]==target)
        return end;
        
    return -1;
}

二分花花模板，最后返回的L要按条件调整

#左闭右开 [l,r)  注意这里好像r = n+1，但是可能溢出
def binarySearch(l,r):
    while l < r:
        m = l + (r-l)/2
        if g(m): 
            r = m #new range[l,m)
        else:
            l = m + 1 # new range[m+1,r)
    return l

#闭合区间 [l,r]
def binary_search(l,r):
    while l <= r:
        m = l + (r-l)/2
        if g(m):
            r = m - 1
        else:
            l = m + 1
    return l

Bisect

核心区别

方法	返回值位置	当元素存在时	当元素不存在时	相等元素处理
bisect_left	插入位置在最左边	返回第一个等于x的位置	返回应该插入的位置	所有相等元素左边
bisect_right	插入位置在最右边	返回最后一个等于x的位置+1	返回应该插入的位置	所有相等元素右边

面试中如何选择

使用 bisect_left 的情况

1. 查找元素是否存在（替代in操作）

   pythonCopy

   def contains(arr, x):
       i = bisect.bisect_left(arr, x)
       return i != len(arr) and arr[i] == x

2. 寻找第一个≥x的元素

   pythonCopy

   first_ge = arr[bisect.bisect_left(arr, x)]

3. 需要精确位置时

   • 如区间问题中找不重叠的最后一个区间

4. 实现有序集合

   • 保证相同元素插入位置一致

使用 bisect_right 的情况

1. 计算元素出现次数

   pythonCopy

   count = bisect.bisect_right(arr, x) - bisect.bisect_left(arr, x)

2. 寻找最后一个≤x的元素

   pythonCopy

   last_le = arr[bisect.bisect_right(arr, x) - 1]

3. 需要插入到重复元素之后

   • 如维护按时间排序的日志，新事件插入到相同时间事件的末尾

记忆技巧

1. "Left"联想:

   • 左边界 → 第一个等于x的位置

   • 如C++中的lower_bound

2. "Right"联想:

   • 右边界 → 最后一个等于x的位置+1

   • 如C++中的upper_bound

3. 插入场景想象:

   • bisect_left插入后元素在相同值的最前面

   • bisect_right插入后元素在相同值的最后面