while不取等，找小于等于target，判断右边界

整数的二分查找

Y总的两个板子：
理解：我感觉不管是整数还是浮点数，他们的本质都是找到check(mid)满足这个条件的l下标，或者l代表的数，这是本质。

  1. bool check(int x) {/* ... */} // 检查x是否满足某种性质
  3. // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
  4. int bsearch_1(int l, int r)
  5. {
  6.     while (l < r)
  7.     {
  8.         int mid = l + r >> 1;
  9.         if (check(mid)) r = mid;    // check()判断mid是否满足性质
  10.         else l = mid + 1;
  11.     }
  12.     return l;
  13. }
  14. // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
  15. int bsearch_2(int l, int r)
  16. {
  17.     while (l < r)
  18.     {
  19.         int mid = l + r + 1 >> 1;
  20.         if (check(mid)) l = mid;
  21.         else r = mid - 1;
  22.     }
  23.     return l;
  24. }

根据例题对上面的板子进行讲解和理解
image.png
上面图的红和绿之前的区间本质是下面题要求的那部分，位置就是下面要求的答案

  • acwing 789.数的范围

自己的理解：
下面 a[mid] >= x的时候，找到满足这个check的第一个下标，如果不存在==的情况，那么找到的一定是最小的，并且大于x的下标！！！！
同理第二个，也是找到满足a[mid] <= x的时候，找到满足第一个下标

  1. #include <iostream>
  2. using namespace std;
  4. const int N = 1e5 + 10;
  5. int n , m;
  6. int a[N];
  8. int main() {
  9.     scanf("%d%d", &n, &m); // m作为查询次数
  10.     for (int i = 0; i < n ; i++) {
  11.         scanf("%d", &a[i]);
  12.     }
  14.     while (m--) {
  15.         int x;
  16.         scanf("%d", &x); // m次查询，每次查询的内容
  18.         int  l = 0, r = n - 1; // 开始应用板子，目的是为了选出第一个大于等于x的位置。如果
  19.         //元素不存在，选出的l或者事r本质是第一个大于x元素的位置。
  20.         while (l < r) {
  21.             int mid = l + r >> 1; // 这里实际做题的时候先写上 l + r >> 1;后面true的时候 r = mid的不用变，后面如果是 l = mid必须+1
  22.             if(a[mid] >= x) r = mid; // 首先if里面本质就是上面板子的check,r的取值也是需要根据实际解答
  23.             else l = mid + 1; // 这里不用思考，上面确定以后，直接可以确定
  24.         }
  25.         if (a[l] != x) cout << "-1 -1" << endl; // 如果存在，板子一定找得到，但是不存在，很明显，上面的板子二分查找的是满足第一个大于x的位置。
  26.         else {
  27.             cout << l << " ";
  28.             int l = 0, r = n - 1;
  29.             while (l < r) {
  30.                 int mid  = l + r  + 1 >> 1;
  31.                 if (a[mid] <= x)  l = mid; // 因为true的时候，l = mid所以上面mid防止无线循环，必须 +1;
  32.                 else r = mid - 1;
  33.             }
  34.             cout << l << endl;
  35.         }
  36.     }    
  37. }

实用算法的二分查找（他是假定了数组中一定存在要查找的元素了）

  1. int l = 0;
  2. int r = n - 1;
  3. while (l <= r)
  4. {
  5.     int mid = l + r >> 1;
  6.     if (a[mid] > x) r = mid;
  7.     else if (a[mid] < x) l = mid + 1;
  8.     else return mid;
  9. }
  • 这是实用算法使用的算法，加入1,3,5,7是数组中的四个元素，你找4的时候，直接返回就是不对

    浮点数的二分查找应用

    开根号

    下面的相当于是一个求一个double数据开根号。

对这里的理解：
找到满足mid * mid <= x，并且l和r几乎相等的情况

  1. #include <iostream>
  2. using namespace std;
  4. int main() {
  5.     double x;
  6.     cin >> x; 
  7.     double l = 0, r = x; // 因为开根号，数据一定在 0到x，相当于找一个区间内的某个元素
  8.     while (r - l > 1e - 6) { // 下面输出的时候，如果输出四位小数，这里-6就能满足要求，下面输出每加一位，这里-6对应变成-7
  9.         double mid = (l + r) / 2;
  10.         if (mid * mid <= x) l = mid; // 这里就是浮点数的好处，没有所谓的边界问题。对于l和r的更新操作全部都是一样的。
  11.         else r = mid;
  12.     }
  13.     cout << l;
  14.     return 0;
  15. }

求一个数的三次根号

这里和上面二次根号的很明显的一点，l 可以是一个负数，这就导致，如果采用根号的方式，我把范围定界在输入的数的范围之内，l会出现问题。

幸好做的题目规定数的范围 -10000 到 10000

  1. #include <iostream>
  3. using namespace std;
  5. int main() {
  6.     double x;
  7.     cin >> x;
  9.     double l = -10000, r = 10000;
  10.     while (r - l > 1e-8) {
  11.         double mid  = (l + r) / 2;
  12.         if (mid * mid * mid <= x) l = mid;
  13.         else r = mid ;
  14.     }
  15.     printf("%lf", l);
  16.     return 0;
  17. }

lc剑指offer53

image.png

  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         int l = 0, r = nums.size() - 1;
  5.         while (l < r)
  6.         {
  7.             int mid = l + r >> 1;
  8.             if (nums[mid] >= target) r = mid;
  9.             else l = mid + 1;
  10.         }
  11.         int cnt = 0;
  12.         int si = nums.size();
  13.         while (l <= si - 1)
  14.         {
  15.             if (nums[l] == target)
  16.                 cnt++;
  17.             else break;
  18.             l++;
  19.         }
  20.         return cnt;
  21.     }
  22. };

35搜索插入位置

二分过程修改，y总模板必须有更改变化，开始和末尾的时候
image.png

  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.         int l = 0;
  5.         int si = nums.size();    
  6.         int r = si - 1;
  7.         if (si == 1)
  8.         {
  9.             if (target <= nums[0])
  10.                 return 0;
  11.             else return 1;
  12.         }
  13.         int mid;
  14.         while (l < r) {
  15.             mid = l + r >> 1; 
  16.             if(nums[mid] >= target) r = mid; 
  17.             else l = mid + 1; 
  18.         }
  19.         if (l == si - 1 && nums[l] < target) return si;
  21.         return l;
  22.     }
  23. };

剑指11寻找数组的最小数字

旋转数组最重要的一点，以后见到直接找最小值，进行分界，如果是找最大值的话，最小值直接
（idx + size - 1）% size 返回就可以
如果数组存在重复元素，只需要r = r - 1就可以。

用最大值的方式也不是不行，就是会比较麻烦

下面的题解讲解这类题讲解的非常清楚
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/er-fen-cha-zhao-wei-shi-yao-zuo-you-bu-dui-cheng-z/

一定注意这里找的是最小的，最后一定剩下两个数，找较小的时候，mid需要和left相等，如果是找比较大的时候，这个时候mid和right相等，这个时候mid = l + r + 1 >> 1来实现。
y总的模板可以套路，首先这个题不是完整的递增和递减，其次得知道怎么写判断条件。几乎是一个背过的题目，很难自己想出来。知道二分也难想。中间大于右边，一定在右边，mid+1——r,小于左边，r = mid，不是mid - 1，等于的时候无法判断左边右边，就直接r = r - 1;
image.png

重复数组求最小值

  1. class Solution {
  2. public:
  3.     int minArray(vector<int>& numbers) {
  4.         int l = 0;
  5.         int si = numbers.size();
  6.         int r = si - 1;
  7.         while (l < r)
  8.         {
  9.             int mid = l + r >> 1;
  10.             if (numbers[mid] > numbers[r]) l = mid + 1;
  11.             else if (numbers[mid] < numbers[l]) r = mid;
  12.             else r = r - 1; 
  13.         }
  14.         return numbers[l];
  15.     }
  16. };

重复的数组求解最大值的代码

  1. class Solution {
  2. public:
  3.     int minArray(vector<int>& nums) {
  5.         int l = 0, r = nums.size() - 1;
  6.         while (l < r)
  7.         {
  8.             int mid = l + r + 1>> 1;
  9.             if (nums[l] < nums[mid]) l = mid;
  10.             else if(nums[l] > nums[mid]) r = mid - 1;
  11.             // 和上面的最小值的最大的区别，你试一下就可以，2，1，2，2这种的就会导致错过第一个2，相等的时候就得从右边r = r - 1
  12.             else if (nums[l] == nums[mid] && nums[l] == nums[l + 1]) l = l + 1; 
  13.             else r = r - 1;
  15.         }
  16.         return nums[(l + 1) % nums.size()];
  17.     }
  18. };

不重复的旋转数组找最小值

本质和上面的题是一样的，求解最小值的时候，中间值和nums[right]比较，小于的时候r = mid, 大于的时候 l = left + 1,跟左边比的时候，同样都是nums[mid] > nums[left]，最小值在左边区间和右边区间都有可能。上个题目的链接讲述的非常清楚。
image.png

  1. class Solution {
  2. public:
  3.     int findMin(vector<int>& nums) {
  4.         int l = 0, r = nums.size() - 1;
  5.         while (l < r)
  6.         {
  7.             int mid = l + r >> 1; // 求解最小值，求解的目标值偏向左边，具体看链接
  8.             if (nums[mid] > nums[r])  // 只要大于，最小值一定不是mid，
  9.                 l = mid + 1;
  10.             else 
  11.                 r = mid; // 小于的时候可能存在最小值
  12.         }
  13.         return nums[l];
  14.     }
  15. };

找最大值的方式，右边就是最小值的思路找到最小值

  1. class Solution {
  2. public:
  3.     int findMin(vector<int>& nums) {
  4.         int l = 0, r = nums.size() - 1;
  5.         while (l < r)
  6.         {
  7.             int mid = l + r + 1 >> 1; // 两个元素的时候，mid和right相等，因为序列是递增的序列
  8.             if (nums[mid] > nums[l])  // 最后
  9.                 l = mid;
  10.             else 
  11.                 r = mid - 1;
  12.         }
  13.         return nums[(l + 1) % nums.size()];
  14.     }
  15. };

搜索旋转数组

  • 这个题就是上面题解应用，先找到最小值，用二分的方法。然后选择一个区间继续查找。

image.png

  1. class Solution {
  2. public:
  3.     int bound(int l, int r, vector<int>& nums, int target)
  4.     {
  5.         int i = r;
  6.         while (l < r)
  7.         {
  8.             int mid = l + r >> 1;
  9.             if (nums[mid] >= target) r = mid;
  10.             else l = mid + 1;
  11.         }
  12.         if (l <= i && nums[l] != target) return -1;
  13.         else return l;
  14.         return -1;
  15.     }
  17.     int search(vector<int>& nums, int target) {
  18.         if (nums.size() == 1) return nums[0] == target? 0 : -1; 
  19.         int l = 0, r = nums.size() - 1;
  20.         while (l < r)
  21.         {
  22.             int mid = l + r >> 1;
  23.             if (nums[mid] > nums[r]) l = mid + 1;
  24.             else r = mid;
  25.         }
  26.         if (l == 0) return bound(0, nums.size() - 1, nums, target);
  27.         int idx = -1;
  28.         if (nums[0] > target) {
  29.             return bound(l, nums.size() - 1, nums, target);  
  30.         } else {
  31.             return bound(0, l - 1, nums,  target);
  33.         }
  34.         return idx;
  35.     }
  36. };

好的题解
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/duo-si-lu-wan-quan-gong-lue-bi-xu-miao-dong-by-swe/

山脉寻找目标值

42D3FA67-A59E-44A1-AE12-301BB22C0E6F.png

本质也是利用二分查找，但是和上面找最大最小值不一样，因为判断条件是不一样的

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    int search1(int l, int r, MountainArray& mountainArr, int target)
    {   

        while (l < r)
        {
            int mid = l + r >> 1;
            if (mountainArr.get(mid) >= target) r = mid;// 逆序的时候能不能用
            else l = mid + 1;
        }
        if (mountainArr.get(l) != target) return 0x3f3f3f3f;
        else  return l;
    }


    int search2(int l, int r, MountainArray& mountainArr, int target)
    {   

        while (l < r)
        {
            int mid = l + r >> 1;
            if (mountainArr.get(mid) <= target) r = mid;// 逆序的时候换成小于等于就可以。找的目标值就是下标小于等于目标值的第一个位置
            else l = mid + 1;
        }
        if (mountainArr.get(l) != target) return 0x3f3f3f3f;
        else  return l;
    }
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int l = 0, r = mountainArr.length() - 1;
        while (l < r)
        {
            // 这里没有+1，保证l和mid只要在while循环里面，就是想等的，
            //并且两个元素的时候 l = mid = r - 1;这样下面的判断就永远不会越界    
            int mid = l + r >> 1; 

             if (mountainArr.get(mid) < mountainArr.get(mid + 1)) 
                l = mid + 1; 
             else 
                r = mid;
        }
        int idx1 = search1(0, l, mountainArr, target);
        // 注意求idx2的时候是逆序的，逆序需要使用第二个search函数
        int idx2 = search2(l + 1, mountainArr.length() - 1, mountainArr,  target);

        int res = min(idx1, idx2);
        return res == 0x3f3f3f3f ? -1 : res;
    }
};