挑战20天刷完leecode100

2025.1.5 

二分查找

1 搜索插入位置

就是简单的二分查找 注意开闭就行

这里有一句话就是nums是升序的 如果他不是严格递增 就是有相同的数字的情况下应该怎么写?

  int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = (int) nums.size() - 1; 
        while (left <= right) { // 区间不为空
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1; // 范围缩小到 [left, mid-1]
            } else {
                left = mid + 1; // 范围缩小到 [mid+1, right]
            }
        }
        // 循环结束后 left = right+1
        // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }

这是代码！  就是在这里需要更改

2 搜索二维矩阵

第一个方法就是通过两个二分 第一个二分确定在哪一行第二个确定在那一列 这里可以用3的方法一样的

第二个方法就是通过从最后一行第一列开始，每次去除一行或者一列这个简单

3 在排序数组中查找元素的第一个和最后一个位置

我们就是写一个lower_bound （第一个大于等于当前target的元素的下表！）

4搜索旋转排序数组

分组二分查找 

如果[left - mid）他是有序地我们就看target是不是在这中间不是的话left = mid+1（不在的话一定在右侧）

如果（mid,right ] 他是有序地我们就看target是不是在这中间不是的话right = mid-1(不在中间一定是在左侧 )

5