# 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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l2er-fen-cha-zhao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.