> 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/chapter1.md).

# Binary Search and Sorted Array

二分法

1. 给有序整数组nums，找出***any/first/last position of target*** in nums，通常找临界点。
2. 复杂度 log（n）
3. * 使用 `start + 1 < end` 是为了保证 **start 和 end 在循环退出时总是相邻**。
   * 退出循环后，你可以单独检查 `nums[start]` 和 `nums[end]`，从而准确找到目标值的位置。
4. mid=start+(end-start)/2 即使Integer很大也不会溢出
5. 二分查找的模版，**找第一次出现的位置。** 注意可能出现多次，所以当找到这个数字的时候(==)不能直接结束，**而要将end移动到mid处**。 直到最后缩小到只有一个或两个数字时，**优先判断start，**&#x518D;判断end。同理寻找**first/last/any occurence of the target,** any找到就立刻返回，first每次==移动右边，last每次==移动左边。
6. 使用条件：

   * **排序数组**：查找值或范围（如标准二分）。
   * **优化时间复杂度**：用 O(log n) 替代 O(n)，如找边界、特定位置。
   * **数组分割**：找到分割点，使一部分满足条件，另一部分不满足。最优分割点
   * **最优值问题**：搜索满足条件的最小/最大值（如分配问题、搜索区间问题）。

   **二分查找的例子**

   * **分配问题**：分配工作、分割数组，使得分配的最大工作量最小。
   * **最大/最小值问题**：如在一段时间内完成任务的最短时间。

   ####
7. #### **二分查找和动态规划的对比**

   * **二分查找**：如果目标是优化某个参数（如时间、成本）并且**满足单调性。**
     * 例子：找能满足条件的最小时间。
   * **动态规划**：如果优化目标需要子问题结果。

     * 例子：从一组选项中找到最优路径或组合。

   #### **总结：双向指针和快速排序的循环条件**

   * **双向指针**
     * `start < end`：处理相邻元素。
     * `start <= end`：覆盖所有可能的情况。
   * **快速排序**
     * 通常使用 `start < end`，避免多余的循环。不依赖Mid，双指针只需要不交叉就能完成任务。
   * **二分查找**
     * 使用 `start + 1 < 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;
}
```

二分查找range

range先找左bound，每次移动end，找右Bound，(可能因为左边的肯定都比左边界小，所以移动右边，右边界同理)每次移动start,中间要reset start和end

二分查找matrix

从左下或者右上。这样每次都可以排除一行或者一列。普通正向或者反向都不好用

```
start =0, end = row * column -1;
int number = matrix[mid / column][mid % column]; //都是用column
```

**三步翻转法**

三步翻转法可以实现rotated和rotate数组还原

先局部后整体，前n-k段和后面K段各自翻转，拼接后整体翻转

中间用到reverse一个数组/链表，模板窍门，首尾呼应。

```
def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next  # Save the next node
        curr.next = prev      # Reverse the link
        prev = curr           # Move prev to the current node
        curr = next_node      # Move to the next node
    return prev
```