Binary Search and Sorted Array

二分法

给有序整数组nums，找出any/first/last position of target in nums，通常找临界点。
复杂度 log（n）
- 使用 start + 1 < end 是为了保证 start 和 end 在循环退出时总是相邻。
- 退出循环后，你可以单独检查 nums[start] 和 nums[end]，从而准确找到目标值的位置。
mid=start+(end-start)/2 即使Integer很大也不会溢出
二分查找的模版，找第一次出现的位置。 注意可能出现多次，所以当找到这个数字的时候(==)不能直接结束，而要将end移动到mid处。直到最后缩小到只有一个或两个数字时，优先判断start，再判断end。同理寻找first/last/any occurence of the target, any找到就立刻返回，first每次==移动右边，last每次==移动左边。
使用条件：
- 排序数组：查找值或范围（如标准二分）。
- 优化时间复杂度：用 O(log n) 替代 O(n)，如找边界、特定位置。
- 数组分割：找到分割点，使一部分满足条件，另一部分不满足。最优分割点
- 最优值问题：搜索满足条件的最小/最大值（如分配问题、搜索区间问题）。
二分查找的例子
- 分配问题：分配工作、分割数组，使得分配的最大工作量最小。
- 最大/最小值问题：如在一段时间内完成任务的最短时间。
二分查找和动态规划的对比
- 二分查找：如果目标是优化某个参数（如时间、成本）并且满足单调性。
  - 例子：找能满足条件的最小时间。
- 动态规划：如果优化目标需要子问题结果。
  - 例子：从一组选项中找到最优路径或组合。
总结：双向指针和快速排序的循环条件
- 双向指针
  - 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

PreviousGraph and Search NextFind Minimum in Rotated Sorted Array

Last updated 1 month ago

二分查找和动态规划的对比

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