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


---

# 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/chapter1.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.