> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l2er-fen-cha-zhao.md).

# 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`插入后元素在相同值的最后面

<br>