二分算法

一分为二，化繁为简

思路

1. 预处理–数组有序，不是有序则 先排序
2. 二分查找–将数组一分为二
3. 后处理–剩余一半数组中查找可行的范围

三个模板

模板一

// 二分查找 --- [left, right]
// 数组已经是有序的了!
int binarySerach1(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        // 防止溢出 等同于(left + right)/2
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] > target) {
            // target 在左区间，所以[left, middle - 1]，如果是right = mid，则划分后的区间重新包含了已经判断过的mid值
            right = mid - 1;
        }
        else {
            // target 在右区间，所以[middle + 1, right]
            left = mid + 1;
        }
    }

    return -1;
}

X的平方根

题目

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

解题思路

找x的平方根，其实就是找一个使n * n <= x 成立的最大的 n。

代码

/*[left,right]解法*/
int MySqrt1(int x){
    int left = 0, right = x;
    int ans = -1;
    while(left <= right){
        int mid = (right - left) / 2 + left;
        if(mid * mid <= x){
            ans = mid;
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    return ans;
}

模板二

// 二分查找 --- [left, right)
// 数组已经是有序的了!
int binarySearch2(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;
    // 定义target在左闭右开的区间里，即：[left, right)
    int left = 0, right = nums.length;
    // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            //  target 在右区间，在[middle + 1, right)中
            left = mid + 1;
        }
        else {
            // target 在左区间，在[left, middle)中
            right = mid;
        }
    }
    // 结束条件: left == right
    if (left != nums.length && nums[left] == target) return left;
    return -1;
}

X的平方根

[left,right)解法

/*[left,right)解法*/
int MaSqrt2(int x){
    int left = 0, right = x + 1;
    int ans = -1;
    while(l < r){
        int mid = (right - left) / 2 + left;
        if(mid * mid <= x){
            ans = mid;
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }
    return ans;
}

模板三

// 二分查找 --- (left, right)
// 数组已经是有序的了!
int binarySearch3(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            //  target 在右区间，在(middle, right)中
            left = mid;
        }
        else {
            // target 在左区间，在(left, middle)中
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if (nums[left] == target) return left;
    if (nums[right] == target) return right;
    return -1;
}

X的平方根

(left,right)解法

/*(left,right)解法*/
int MySqrt3(int x){
    int left = -1, right = x + 1;
    int ans = -1;
    while(left + 1 < right){
        int mid = (right - left) / 2 + left;
        if(mid * mid <= x){
            ans = mid;
            left = mid;
        }
        else{
            right = mid;
        }
    }
    return ans;
}

区别

1. 初始边界left和right不同
2. while()内判断条件不同
3. left和right后处理的不同

首先明白我们二分搜索的区间是怎么划分的。

初始化边界

• 如果是[left,right]，那么left = 0，right = nums.size() - 1。这样刚好包含nums数组全部数组，如果right = nums.size()，则多包含了一个数组外的数

• 如果是[left,right)，那么left = 0，right = nums.size()。跟[]不同，right = nums.size()时才能刚好把数组包含，如果right = nums.size() - 1，则会少一个右边界元素。

• 如果使(left,right)，那么left = -1，right = nums.size()。

while内判断条件

不断将区间一分为二，当出现不合法的区间时中断循环。

• [left,right]，只需要判断条件合法即可，left <= right情况可能出现，如果选择left < right则少了一个循环
• [left,right)，不可能出现left = right，因此left< right即可决定循环是否中止
• (left,right)，left 也不能使用left 与 right是否相等来中止循环，当left - 1 = right(此情况不存在)时就需要中止循环

left right后处理

根据区间类型看mid是否在二分后的区间内来决定后处理。
为方便处理，改为寻找与target相等的下标（为方便表述，mid代表下标为mid的数组值）

• [left,right]
  • mid < target，如果left = mid，划分后的区间仍然包含已经进行判断过的mid，因此应该为mid + 1。
  • mid > target，如果right = mid，划分后的区间仍然包含…
  • mid = target，找到结果，返回
• [left,right)
  • mid < target，left = mid即可满足划分后的区间不包含判断过的mid（右开）
  • mid > target，left = mid + 1，同左闭
  • mid = target，不会有这种情景，在left - 1 = right循环就中止了
• (left,right)
  • mid < target，left = mid
  • mid > target，right = mid
  • mid = target，不会有这种情景，在left - 1 = right循环就中止了

总结

对于不同的问题，以上三种模板其实都可以使用，不过是实现方法的不同而已。对于不同的问题选择不同的模板可以有助于代码的理解与实现。

例题

搜索插入的位置

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = (r - l) / 2 + l;
            if(nums[mid] < target){
                l = mid + 1;//如果mid一直小于targrt，则l会大于nums.size() - 1,即插入位置为末尾
            } 
            else{
                r = mid - 1;
            }
        }
        return l;
    }
};

这个代码是抄的别人的，自己写的巨麻烦😫。

总结

该题相当于找最后一个小于target的下一个下标（或者说第一个大于或等于target的数组值的下标），随着循环进行，l代表的是最后一个小于target的下一个下标，而r代表的是第一个大于等于target的数组值的上一个下标，我们要返回的是最后一个小于target的下一个下标，即l。

对于题目要求的结果，我们要分析并总结出其对应的编程语言，并理解left，right对应的是什么。

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

题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

思路一

根据二分特性，随着循环进行，l代表的是最后一个小于target的下一个下标，而r代表的是大于等于target的上一个下标，而本题要求第一个和最后一个元素位置，因此可以使用两次二分，分别找第一个最后一个。

代码

vector<int> searchRange(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    int first = -1, last = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            first = mid;
            r = mid - 1; // 重点
        }
        else if (nums[mid] > target) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    // 最后一个等于target的位置
    l = 0;
    r = nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            last = mid;
            l = mid + 1; // 重点
        }
        else if (nums[mid] > target) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return vector<int>{first, last};
}

总结

还是要使用相等这一利器，不能为了用之前的方法而硬解。此题会有找不到的情况，可能越界，必须使用相等。
而上一题

思路二

当找到target时，将l和r缩小，直到nums[l]和nums[r]都等于target，然后返回

当找不到target时，循环终止，直接返回{ -1, -1}

代码

vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                while (nums[l] != target) {
                    l++;
                }
                while (nums[r] != target) {
                    r--;
                }
                return vector<int>{l,r};
            }
        }
        return {-1,-1};
    }

搜索旋转排序数组

题目

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

代码

回想二分搜索的思想，一分为二，化繁为简！
本题刚拿到手可能会无从下手，想想该如何一分为二？

对于旋转后的数组，一分为二后一定有一半是有序的，另一半无序。
有序的那一半可以根据区间边界值判断target是否在该区间，无序的那一半同样可以根据边界值来判断（边界一定是最大的）

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() -1;

    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (target == nums[mid]) return mid;//因为后面都要进行判断，写在开始即可省略后面二分后的每次判断

        if (nums[l] <= nums[mid])//先判断此次区间是否有序
        {//如果有序，先判断target是否在该区间
            if (target >= nums[l]/*为什么是>=*/ && target < nums[mid])//因为区间是[]的，边界值同样要进行判断，而nums[m]在上面已经判断过相等情况了
                r = mid-1;//如果在就在该区间二分搜索
            else
                l = mid+1;//不在就调整区间，去到另一半无序区间搜索
        }
        else
        {//如果前半部分无序，则后半部分有序，同样先进行判断target是否在该区间
            if (target > nums[mid] && target <= nums[r]/*为什么是<=*/)//同上
                l = mid +1;//如果在该区间，就二分搜索
            else
                r = mid -1;//如果不在就跳出
        }
    }
    return -1;
}

总结

寻找旋转排序数组中的最小值

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

代码

题目转换一下思路，其实就是找到最后一个小于ans初始值的数（用到向上取整）

int findMin(vector<int>& nums) {
    int ans = nums[0];
    int l = 0, r = nums.size() - 1;
    while(l <= r){
        int m = (r - l + 1) / 2 + l;
        if(nums[l] < nums[m]){
            if(nums[l] < ans){
                ans = nums[l];
            }
            l = m + 1;
        }
        else{
            if(nums[m] < ans){
                ans = nums[m];
            }
            r = m - 1;
        }
    }
    return ans;
}

总结

向上取整在搜索最后一个满足条件时使用。