基础算法-二分

二分查找的再梳理Update

分清两种情况男左女右

$[mid,r]$ $l = mid,r = mid - 1$ ; mid = (l + r + 1) >> 1;
$[l,mid]$ $r = mid,l = mid + 1$ ; mid = (l + r) >> 1;

//找有序数组的起始位置
vector<int> a(n + 1);
for(int i = 0;i < n;i++) cin >> a[i];
while(q--){
    int x;cin >> x;
    int l = 0,r = n - 1;
    while(l < r){
        int mid = (l + r) >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if(a[l] != x) cout << "-1 -1" << endl;
    else{
        cout << l << " ";
        l = 0,r = n - 1;
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(a[mid] <= x) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
}

二分查找算法的应用范围

在有序数组中进行查找一个数（二分下标）

如果数据存放在链表中，访问一个元素我们都得通过遍历，有遍历的功夫我们早就找到了这个元素，因此，在链表中不适合使用二分查找。

其中「有序」这个条件可以放宽，半有序数组或者是山脉数组里都可以应用二分查找算法。

旋转和山脉数组的值都有规律可循，元素的值不是随机出现的，在这个特点下，「减治思想」就可以应用在旋转数组和山脉数组里的一些问题上。我们可以把这两类数组统一归纳为部分有序数组

这种二分法用于查找一个有范围的数，也被称为「二分答案」，或者「二分结果」，也就是在「答案区间」里或者是「结果区间」里逐渐缩小目标元素的范围；

二分查找算法的两种思路

思路 1：在循环体中查找元素思路 2：在循环体中排除目标元素一定不存在的区间

二分查找的时间复杂度

大 O 不在乎常数差距，只在乎增长趋势。
故 O(2⋅logn)=O(logn)

推导 $\frac{n}{2^{k}}=1$

$k=\log_{2}{n}$

二分查找例用-二分下标

1基础-搜索元素位置

while(left <= right){
    int mid = left + (right - left)/2;
    if (nums[mid] == target){
        return mid;
    }
    else if (nums[mid] > target){
        right = mid - 1;
    }
    else{
        left = mid + 1;
    }
}

2基础-搜索元素位置递归写法

public static int search(int[] nums, int target) {
    return binarySearch(nums, target, 0, nums.length - 1);
}

private static int binarySearch(int[] nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] > target) {
        return binarySearch(nums, target, left, mid - 1);
    } else {
        return binarySearch(nums, target, mid + 1, right);
    }
}

3基础-在有序数组中查找元素的第一个和最后一个位置

方法	思路	时间复杂度	是否符合题目要求
线性扩展法	找到一个目标后向左右扩展	O(n)	不符合
二分两次法	分别用二分找左边界和右边界	O(log n)	符合

public int[] searchRange(int[] nums, int target) {
    int left = find(nums, target, true);  // 左
    int right = find(nums, target, false); // 右
    return new int[]{left, right};
}
private int find(int[] nums,int target,boolean isLeft){
    int right = nums.length - 1,left = 0;
    int bound = -1;
    while(left <= right){
        int mid = left + (right - left)/2;
        if(nums[mid] == target){
            bound = mid;
            if(isLeft){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        else if(nums[mid] > target){
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    return bound;
}

4旋转数组-无重复寻找最小值

边界处理

情况一：nums[mid] > nums[right]

说明 最小值一定在右边（mid 不可能是最小值）。因为 nums[mid] 比 nums[right] 大，说明从 mid+1 到 right 这段区间里一定有更小的值。

所以我们可以放心地写：

left = mid + 1;

情况二：nums[mid] < nums[right]

说明 最小值在左边，而且 mid 本身可能就是最小值。

所以不能丢掉 mid，只能写：

right = mid;

保留 mid 继续判断。

当 left == right 时，就是最小值的下标。

-> 绕路 mid左右加和不影响复杂度但只需要判断 哪一边有序，或者 最小值在哪一边，就能决定收缩方向

public int findMin(int[] nums) {
     int left = 0;
     int right = nums.length - 1;

     while(left < right){
         int mid = left + (right - left)/2;
         if(nums[mid] > nums[right]){
            left = mid + 1;
         } else{
            right = mid;
         }
     }
     return nums[right];
}

旋转数组有重复最小值 II

while(left < right){
     int mid = left + (right - left)/2;
     if(nums[mid] > nums[right]){
        left = mid + 1;
     } else if(nums[mid] < nums[right]){
        right = mid;
     } else{
        right--;
     }
 }
 return nums[right];

5搜索旋转数组无重复

法一先找最小值，将数组拆分

public int search(int[] nums, int target) {
    int mainIndex = searchMin(nums);

    int leftIndex = getBound(nums,target,0,mainIndex - 1);//左面
    int rightIndex = getBound(nums,target,mainIndex,nums.length - 1);//右面

    if (leftIndex != rightIndex) return Math.max(leftIndex,rightIndex);
    else return -1;

}
private int getBound(int[] nums,int target,int left,int right){
    while(left <= right){
        int mid = left + (right - left)/2;
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] > target){
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    return -1;
}
private int searchMin(int[] nums){
    int left = 0;
    int right = nums.length - 1;

    while(left < right){
        int mid = left + (right - left)/2;

        if (nums[mid] < nums[right]){
            right = mid;
        }
        else if (nums[mid] > nums[right]){
            left = mid + 1;
        }
    }
    return right;
}

法二一步二分法

每次二分时，至少有一半区间是有序的。

if nums[left] <= nums[mid] → 左边有序
否则右边有序。

判断 target 是否在有序区间里。

如果在，就缩小到有序区间；
如果不在，就缩小到另一半。

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] == target) return mid;

    // 左边有序
    if (nums[left] <= nums[mid]) {
        if (target >= nums[left] && target < nums[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    } 
    // 右边有序
    else {
        if (target > nums[mid] && target <= nums[right]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
}

6搜索旋转数组有重复数组 II

法一两步失效

小云同学还期望改造刚才的无重复数组但她考虑到时间复杂度在最坏情况下退化为 O(n) 故给搜索最小数的时候也加上了 right--;但很不幸无法 AC（280/282）

样例是

nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1] target = 2

她发现在有大量重复元素的情况下（如样例），searchMin 找到的 旋转点位置不唯一，从而导致分段二分出错她终于发现是算法思路限制无法通过修补通过这个样例

法二

while(left <= right){ //错点 1
    int mid = left + (right - left)/2;

    if(nums[mid] == target) return true;

    // 遇到重复元素无法判断哪边有序
    if(nums[left] == nums[mid] && nums[mid] == nums[right]){
        left++;
        right--;
    }
    // 左半边有序
    else if(nums[mid] >= nums[left]){
        if(target >= nums[left] && target < nums[mid]){
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 右半边有序
    else {
        if(target > nums[mid] && target <= nums[right]){
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
}

7山脉数组找峰顶索引

while(left < right){
    int mid = left + (right - left)/2;
    if(arr[mid] < arr[mid+1]){
        left = mid + 1;
    }
    else{
        right = mid;
    }
}

8山脉数组中查找目标值

使用相对熟悉的多步二分直接 AC 但请 GPT 大人纠正了一些错误代码习惯摘录在这里

减少重复调用 mountainArr.get(mid)

在 find 和 getmax 中，每次判断都调用了两次 mountainArr.get(mid) 或 mountainArr.get(mid+1)。

二分查找时使用 left <= right 而不是 left < right

原来的 while(left < right) 循环会在循环结束后再单独判断 mountainArr.get(left)，加上上面的优化可以直接写成标准二分查找形式 left <= right，逻辑更干净。

private int getPeak(MountainArray mountainArr){
    int left = 0, right = mountainArr.length() - 1;
    while(left < right){
        int mid = left + (right - left)/2;
        int midVal = mountainArr.get(mid);
        int midNextVal = mountainArr.get(mid + 1);
        if(midVal < midNextVal) left = mid + 1;
        else right = mid;
    }
    return left;
}

private int binarySearch(MountainArray mountainArr, int target, int left, int right, boolean increasing){
    while(left <= right){
        int mid = left + (right - left)/2;
        int midVal = mountainArr.get(mid);
        if(midVal == target) return mid;
        if(increasing){
            if(midVal < target) left = mid + 1;
            else right = mid - 1;
        } else {
            if(midVal > target) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

但通过刚才经验了解不是很熟练一次二分故写了一下有些小问题记录一下

int m2 = mountainArr.get(mid+1); 可能越界

当 mid == mountainArr.length() - 1 时，mid+1 会越界。
在取 m2 前先判断 mid < length - 1，否则不要去访问 mid+1。

但仍不能 AC 对于 样例点输入 [0,5,1] 0 输出 -1 有问题

这才意识到这种做法无法保证返回最小下标故放弃

public int findInMountainArray(int target, MountainArray mountainArr) {
        int left = 0;
        int right = mountainArr.length() - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int m1 = mountainArr.get(mid);

            if(m1 == target) return mid;

            if(mid < mountainArr.length() - 1){ //越界检查
                int m2 = mountainArr.get(mid + 1);
                if(m1 < m2) { //上升区间,m1上升 
                    if(m1 < target) left = mid + 1; //m1小于目标值 去掉左边
                    else right = mid - 1;
                }
                else{ //下降区间
                    if(m1 < target) right = mid - 1;
                    else left = mid + 1;
                }   
            }
            else right = mid - 1; // mid 已经在数组最后，直接往左缩
        }
        return -1;
    }

9小结Boss寻找两个正序数组的中位数

法一：划分法

给定两个正序数组 nums1 和 nums2，求它们合并后的中位数，时间复杂度 O(log(m+n)) 暗示我们不能真的合并数组，而要用「二分法」。

Step1思考

中位数把一个有序数组分成两部分：

左边部分的元素全部 ≤ 右边部分的元素
左边部分和右边部分长度相等（或左边多 1 个）

如果我们能把两个数组合并后的「左边」和「右边」拆开，就能直接得到中位数。

我们希望 leftA + leftB 和 rightA + rightB：

左边所有元素 ≤ 右边所有元素
左边长度 = 右边长度（或左边多 1）

记：

i + j = (m + n + 1) / 2

这个公式保证左右两边长度关系正确（总长度奇偶都通用）

然后要满足：

A[i-1] ≤ B[j]   // A左最大 ≤ B右最小
B[j-1] ≤ A[i]   // B左最大 ≤ A右最小

Step2二分法找 i

为了避免处理太多边界情况，我们规定 A 是短数组（m ≤ n）。

在 [0, m] 范围里二分查找 i
通过指针 left right 算出 i
计算 j = (m + n + 1)/2 - i （有一种向上取整的意味）
检查：
- 如果 A[i-1] > B[j] → i 太大，向左移动
- 如果 B[j-1] > A[i] → i 太小，向右移动
找到满足条件的 i，即划分完成

注意边界处理：

i = 0 → left_A 为空 → A[i-1] = -∞
i = m → right_A 为空 → A[i] = ∞
j = 0 或 j = n 同理

另在 Java 中：

正无穷 → Integer.MAX_VALUE
负无穷 → Integer.MIN_VALUE

在C++中

正无穷 → INT_MAX（<climits> 中定义）
负无穷 → INT_MIN

Step3计算中位数

划分完成后：

max_of_left = max(A[i-1], B[j-1])
min_of_right = min(A[i], B[j])

如果总长度是奇数 → 中位数 = maxofleft
如果总长度是偶数 → 中位数 = (maxofleft + minofright) / 2

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) { //保证nums1是短数组
        return findMedianSortedArrays(nums2, nums1);
    }
    int m = nums1.length;
    int n = nums2.length;
    int left = 0,right = m;//表示可选择的空位

    while(left <= right){
        //i,j 表示切点
        int i = left + (right - left)/2;
        int j = (m + n + 1)/2 - i;

        int A_left = (i == 0) ? Integer.MIN_VALUE : nums1[i-1];// 左面没有元素
        int A_right = (i == m) ? Integer.MAX_VALUE : nums1[i]; // 右面没有元素
        int B_left = (j == 0) ? Integer.MIN_VALUE : nums2[j-1];
        int B_right = (j == n) ? Integer.MAX_VALUE : nums2[j];

        if( A_left <= B_right && B_left <= A_right){ //划分正确
            if ((m + n) % 2 == 0) {
                return (Math.max(A_left, B_left) + Math.min(A_right, B_right)) / 2.0;
            } else {
                return Math.max(A_left, B_left);
            }
        }
        if(A_left > B_right){ //A左最大 > B右最小 i太大 向左移
            right = i - 1; //通过i来影响right
        }
        if(B_left > A_right){// B左最大 > A右最小 i小 向右移
            left = i + 1;
        } 
    }
    return -1;
}

法二直接二分

数学难度较大写了一个还没 AC 的代码比较头晕后清清脑子再补先贴一个题解

二分查找例用-二分答案

特征

答案空间可枚举 + 存在单调性函数 + 能通过函数值判断往左还是往右。

答案在一个范围内，范围可枚举（通常是整数区间）
可以定义一个单调性函数 f(x)，用来判断当前 x 是否「可行」或「过大/过小」。
- 在2题：
  - 定义 count = # {nums[i] ≤ mid}。
  - 若 count > mid → 说明重复数一定在左半边。
  - 单调性：随着 mid 增大，count 只会变大或相等。
- 在3题：
  - 定义 f(x) = sum(min(a, x))。
  - 单调性：随着 x 增大，f(x) 只会变大或相等。
目标是找到某个最优点/最接近点，而不是直接找到某个精确位置。
- 在2题：我们最终要精确锁定唯一的重复数。
- 在3题：我们要让 f(x) 最接近 target，可能会停在两个候选解之间 → 需要比较。

1计算算术平方根

public int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }
    int left = 1;
    int right = x / 2;

    while (left < right){
        int mid = (left + right + 1) / 2; //向上取整

        if (mid > x / mid) {
            // 大于等于mid的数一定不是解，下一轮搜索的区间为 [left, mid - 1]
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    return left;
}

2寻找重复数

二分法

-> 在 值的范围 上做二分，而不是在数组下标上

public int findDuplicate(int[] nums) {
    int left = 1, right = nums.length - 1; // 搜索的值域范围 [1, n]
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        // 统计 <= mid 的元素个数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) count++;
        }
        if (count > mid) {
            // 重复数在 [left, mid]
            right = mid;
        } else {
            // 重复数在 [mid+1, right]
            left = mid + 1;
        }
    }
    return left;
}

在没有重复的情况下：在区间 [1, mid] 里，最多应该有 mid 个不同的数。所以 count ≤ mid。

如果 count > mid：说明在 [1, mid] 这个区间里，元素的数量超过了它本应能容纳的数量，这区间里一定有重复数。 → 因此我们缩小搜索区间到 [left, mid]。

如果 count ≤ mid：说明 [1, mid] 内没有超过容量，重复数只能出现在 [mid+1, right]。

public int findDuplicate(int[] nums) {
    int left = 1, right = nums.length - 1; // 搜索的值域范围 [1, n]
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        // 统计 <= mid 的元素个数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) count++;
        }
        if (count > mid) {
            // 重复数在 [left, mid]
            right = mid;
        } else {
            // 重复数在 [mid+1, right]
            left = mid + 1;
        }
    }
    return left;
}

链表思路-快慢指针

见链表章节(后续更新)

3转变数组后最接近目标值的数组和

第一遍写没有打上调试发现不太对劲有两个错误已标注在代码中

public int findBestValue(int[] arr, int target) {
    int len = arr.length;
    int left = 0,right = findMax(arr,len);
    while(left < right){
        int mid = left + (right - left)/2;
        int count = js(arr,len,mid);
        System.out.println(mid);
        System.out.println(count);
        if(target <= count) right = mid; 
        //错点一 原为right = mid - 1在「最接近目标」的题里，我们不是要严格排除 mid，而是要保留它作为候选值。
        else left = mid + 1;
    }
    int c1 = Math.abs(js(arr,len,left) - target);
    int c2 = (left > 0) ? Math.abs(js(arr, len, left - 1) - target) : Integer.MAX_VALUE;
    //错点二 int c2 = Math.abs(js(arr,len,left - 1) - target); left-1可能越界
    if(c1 == c2) return Math.min(left,left - 1);
    else if(c1 > c2) return left - 1;
    else return left;
}
private int js(int[] nums,int len,int mid){
    int count = 0;
    for(int i = 0;i < len;i++){
        count += Math.min(nums[i],mid);
    }
    return count;
}
private int findMax(int[] nums,int len){
    int max = 0;
    for(int i = 0;i < len;i++){
        max = Math.max(max, nums[i]);
    }
    return max;
}

Search

基础算法-二分

基础算法-二分

二分查找的再梳理Update

二分查找算法的应用范围

二分查找算法的两种思路

二分查找的时间复杂度

二分查找例用-二分下标

1基础-搜索元素位置

2基础-搜索元素位置 递归写法

3基础-在有序数组中查找元素的第一个和最后一个位置

4旋转数组-无重复寻找最小值

边界处理

旋转数组有重复最小值 II

5搜索旋转数组无重复

法一 先找最小值，将数组拆分

法二 一步二分法

6搜索旋转数组有重复数组 II

法一 两步失效

法二

7山脉数组找峰顶索引

8山脉数组中查找目标值

9小结Boss寻找两个正序数组的中位数

法一：划分法

Step1思考

Step2二分法找 i

Step3计算中位数

法二 直接二分

二分查找例用-二分答案

特征

1计算算术平方根

2寻找重复数

二分法

链表思路-快慢指针

3转变数组后最接近目标值的数组和

关键洞察

2基础-搜索元素位置递归写法

法一先找最小值，将数组拆分

法二一步二分法

法一两步失效

法二直接二分