1713得到子序列的最少操作次数：

贪心算法的思想，想要使得子序列最长结尾的元素序号应该尽可能的小，使用二分法来查找第一个大于或者等于目标元素的数据被目标元素替换，来达到序号最小的目的。

162寻找峰值（二分法爬坡，细节满满）

这道题寻找峰值，用爬坡的思想，因为默认num[n] = 负无穷，往递增的地方走，必有峰值。然而若要复杂度为logn，单纯的递归行不通，使用二分法来进行搜索。这题还有一个非常重要的细节，labda表达式的返回值为pair类型的，这是因为下标-1和0默认负无穷，为了使他们能表现出这种特征，他们的first设置为0，正常的pair的first值设置为1。
是因为pair之间的比较都是先比较first然后再比较second。这样就能实现-1 和 n 永远都是最小的情况。
说实话这个pair在这里的设计没什么用，直接二分也能解决，但是提供一种很好的思路。

  1. class Solution {
  2. public:
  3.     int findPeakElement(vector<int>& nums) {
  4.         int n = nums.size();
  5.         int l = 0, r = n;
  6.         auto get = [&](int i)->pair<int,int>{
  7.             if(i == -1 || i == n){
  8.                 return {0, 0};
  9.             } 
  10.             return {1, nums[i]};
  11.         };
  12.         int mid = l + (r - l)/2;
  13.         while(!(get(mid-1) < get(mid)&&get(mid) > get(mid+1))){
  14.             if(get(mid-1) > get(mid)){
  15.                 r = mid;
  16.                 mid = l + (r - l)/2;
  17.             } else if(get(mid) < get(mid+1)){
  18.                 l = mid + 1;
  19.                 mid = l + (r - l)/2;
  20.             } 
  21.         }
  22.         return mid;
  23.     }
  24. };

4.寻找两个正序数组的中位数（这题不是用二分写的，但是思想非常重要）

  • 这一题的主要结构是用一个k来表示取合并之后数组的第k个最小的值，通过维护这个合并之后的数组以及更新k的值，当k=1时目标值就是两个分数组中的一个了。
  • 这里的k的更新使用k-= newindex - index+1这里的加一最好的判别方式就是直接找特殊情况，当newindex等于index的时候，应该删除一个值，k应该减一
  • 需要分开判断是奇数和偶数的情况
  • 应当判断index为边界的情况，此时直接从另一边的第k个数就可以了

  • k是目标数字所在的位置，index1和index2分别是两个数组的目标位置。

    1. class Solution {
    2. public:
    3.   int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
    4.       /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
    5.        * 这里的 "/" 表示整除
    6.        * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
    7.        * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
    8.        * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
    9.        * 这样 pivot 本身最大也只能是第 k-1 小的元素
    10.        * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
    11.        * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
    12.        * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
    13.        */
    15.       int m = nums1.size();
    16.       int n = nums2.size();
    17.       int index1 = 0, index2 = 0;
    19.       while (true) {
    20.           // 边界情况
    21.           if (index1 == m) {
    22.               return nums2[index2 + k - 1];
    23.           }
    24.           if (index2 == n) {
    25.               return nums1[index1 + k - 1];
    26.           }
    27.           if (k == 1) {
    28.               return min(nums1[index1], nums2[index2]);
    29.           }
    31.           // 正常情况
    32.           int newIndex1 = min(index1 + k / 2 - 1, m - 1);
    33.           int newIndex2 = min(index2 + k / 2 - 1, n - 1);
    34.           int pivot1 = nums1[newIndex1];
    35.           int pivot2 = nums2[newIndex2];
    36.           if (pivot1 <= pivot2) {
    37.               k -= newIndex1 - index1 + 1;//相当于(k = k - (newindex - index1 + 1))，剪掉小于的部分。
    38.               index1 = newIndex1 + 1;
    39.           }
    40.           else {
    41.               k -= newIndex2 - index2 + 1;//至于这里为什么要+1，建议从边界来看，当newindex与index相等时，k相当于往前动
    42.               //一位，因此多一个加1
    43.               index2 = newIndex2 + 1;
    44.           }
    45.       }
    46.   }
    48.   double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    49.       int totalLength = nums1.size() + nums2.size();
    50.       if (totalLength % 2 == 1) {
    51.           return getKthElement(nums1, nums2, (totalLength + 1) / 2);
    52.       }
    53.       else {
    54.           return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
    55.       }
    56.   }
    57. };

    53-1.在排序数组中查找数字(查找左右边界)

    这题用到二分法，先找右边界，在找左边界。边界确定就看特殊情况。注意，无论是左闭右开还是左闭右闭都是看l来确定边界

    1. class Solution {
    2. public:
    3.   int search(vector<int>& nums, int target) {
    4.       int n = nums.size();
    5.       int left = 0, right = n;
    6.       while(left < right){
    7.           int mid = left + (right - left)/2;
    8.           if(nums[mid] >= target){
    9.               right = mid;
    10.           } else {
    11.               left = mid + 1;
    12.           }
    13.       }
    14.       int first = left; 
    15.       left = 0, right = n;
    16.       while(left < right){
    17.           int mid = left + (right - left)/2;
    18.           if(nums[mid] > target){
    19.               right = mid;
    20.           } else {
    21.               left = mid + 1;
    22.           }
    23.       }
    24.       return left -first;
    25.   }
    26. };

    53-2 0~n-1中缺失的数字(注意特殊条件)

    二分法，判断的依据是，nums[i]==i。这里没想出来太可惜了。返回值需要思考一下，我刚开始的时候返回的是nums[l]-1，没有考虑到数组越界的情况。因为求出来的l就是缺数的位置，直接返回l即可。

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

    69. Sqrt(x)（巧妙）

    这一题我是用的笨比写法

    暴力

    注意会出现越界，for循环里面必须是long类型，因为c++在计算时如果两个都是int类型会先将结果转存到int类型的空间中。
    例如：
    int i；
    long sum = i + i；（这里可能越界，因为会先将结果转存到int中，然后在转换为long类型）
    正确：
    long i；
    long sum = i + i；

    1. class Solution {
    2. public:
    3.   int mySqrt(int x) {
    4.       for(long i = 0; i <= x; i++){//这里要注意
    5.           long num1 = i*i;
    6.           long num2 = (i+1)*(i+1);
    7.           if(num1==x||(num1<x&&num2>x)){
    8.               return i;
    9.           }
    10.       }
    11.       return 0;
    12.   }
    13. };

    二分法(巧妙)

    我估计会经常使用这个技巧。将一道题目看成是求一个等式的解，然后通过二分法来解决。
    此题就可以看成是 求 f(x) = x**2 - a = 0的解在[0,a]这个区间里面应该有f(x)等于0的解。

    1. class Solution {
    2. public:
    3.   int mySqrt(int x) {
    4.       if(x == 0) return x;
    5.       int l = 1, r = x, mid, sqrt;
    6.       while(l <= r){
    7.           mid = l + (r-l)/2;
    8.           sqrt = x/mid;
    9.           if(sqrt == mid){
    10.               return mid;
    11.           } else if(sqrt < mid){
    12.               r = mid - 1;
    13.           } else {
    14.               l = mid + 1;
    15.           }
    16.       }
    17.       return r;
    18.   }
    19. };

    34. 在排序数组中查找…..（标准二分逼近写法）

    标准写法

    1. class Solution {
    2. public:
    3.   vector<int> searchRange(vector<int>& nums, int target) {
    4.       if(nums.empty()) return {-1, -1};
    5.       int lower = lower_bound(nums, target);
    6.       int upper = upper_bound(nums, target);
    7.       if(lower == nums.size()||nums[lower]!= target){
    8.           return {-1, -1};
    9.       }
    10.       return {lower, upper};
    11.   }
    12. //左侧逼近
    13.   int lower_bound(vector<int>&nums, int target){
    14.       int l = 0, r = nums.size(), mid;
    15.       while(l < r){
    16.           mid = l + (r-l)/2;
    17.           if(nums[mid] >= target){
    18.               r = mid;
    19.           } else {
    20.               l = mid + 1;
    21.           }
    22.       }
    23.       return l;
    24.   }
    25. //右侧逼近
    26.   int upper_bound(vector<int>&nums, int target){
    27.       int l = 0, r = nums.size(), mid;
    28.       while(l < r){
    29.           mid = l + (r-l)/2;
    30.           if(nums[mid] > target){
    31.               r = mid;
    32.           } else {
    33.               l = mid + 1;
    34.           }
    35.       }
    36.       return l - 1;
    37.   }
    38. };

81. 搜索旋转排序数组 II（二分变种）

考验二分的特殊情况。不难把情况分门别类好就行了。

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

154. 寻找旋转排序数组中的最小值 II（旋转数组变种）

这里注意最好和右边比不要和左边界比较。因为数组是从小到大的规则，和左边界比较的时候1234这种递增的情况会判断错误。
注意边界的问题

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

540. 有序数组中的单一元素

这题出现大问题！！！！！！！！！！！！！！！！！！！！！！！！！
0应该写成0<mid&&mid<4

  1. class Solution {
  2. public:
  3.     int singleNonDuplicate(vector<int>& nums) {
  4.         int l = 0, r = nums.size(), n = nums.size();
  5.         if(n==1){
  6.             return nums[0];
  7.         }
  8.         while(l < r){
  9.             int mid = l + (r-l)/2;
  10.             if((0<mid&&mid<n-1&&nums[mid]!=nums[mid+1]&&nums[mid]!=nums[mid-1])||(mid==0&&nums[mid]!=nums[mid+1])||(mid==n-1&&nums[mid]!=nums[mid-1])){
  11.                 return nums[mid];
  12.             } else if(mid>0&&nums[mid]==nums[mid-1]&&mid%2==1||mid<n-1&&nums[mid]==nums[mid+1]&&mid%2==0){
  13.                 l = mid+1;
  14.             } else {
  15.                 r = mid;
  16.             }
  17.         }
  18.         return nums[l];
  19.     }
  20. };

744. 寻找比目标字母大的最小字母

  • 有点类似前面的一题，注意出去的时候的问题

  • 注意越界，避免陷入无线循环

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

    668. 乘法表中第k小的数（hard题目）

  • 这里面的数学推导很重要

  • 这里用的是左闭右开的写法

  • 公式在这里：image.png

    1. class Solution {
    2. public:
    3.   int findKthNumber(int m, int n, int k) {
    4.       int left = 1, right = m * n;
    5.       while (left <= right) {
    6.           int x = left + (right - left) / 2;
    7.           int count = x / n * n;//这里的先除n是向下取整。
    8.           for (int i = x / n + 1; i <= m; ++i) {//根据推导的公式而来
    9.               count += x / i;
    10.           }
    11.           if (count >= k) {//这里的count表示不大于x的数个数总和，
    12.               //因为当count==k时x是有可能为第count+1大的数。
    13.               //因此缩小范围。找到第一个count为k的数。
    14.               right = x-1;
    15.           } else if(count < k){
    16.               left = x + 1;
    17.           } 
    18.       }
    19.       return left;
    20.   }
    21. };

    719. 找出第 K 小的数对距离（巧妙）

    做二分法的题目，一定要想到怎么和二分法挂钩，有时候不是那么简单能够想出来。但是需要找到二分法的切入点，才方便写。

  • 有个疑问，方法一的最后返回的left，如何保证这个left是数组中存在的差值呢？

    • 这就是lower_bound的美妙之处，和668乘法表那个题目类似。如果实际的为[1,100,1000]，那么在这个算法中及时某次中间mid为300，二分法会不断迫使寻找100。这里可以看下面第14行，right = mid - 1。会不断迫近已存在的！！！
      1. class Solution {
      2. public:
      3. int smallestDistancePair(vector<int>& nums, int k) {
      4.    sort(nums.begin(), nums.end());
      5.    int n = nums.size(), left = 0, right = nums.back() - nums.front();
      6.    while (left <= right) {
      7.        int mid = (left + right) / 2;
      8.        int cnt = 0;
      9.        for (int j = 0; j < n; j++) {
      10.            int i = lower_bound(nums.begin(), nums.begin() + j, nums[j] - mid) - nums.begin();//枚举所有数对的右端点j，二分查找大于等于nums[j]-mid的最小值下标i。那么右端点为j且距离小于等于mid的数对数目为j-i，计算这些数目之和。
      11.            //mid为距离，推断 nums[j] - nums[i] <= mid, nums[j] - mid <= nums[i],所以要找到第一个大于等于nums[j]-mid的位置i，满足上述公式。
      12.            cnt += j - i;//这里的cnt计算的应该是小于绝对值差小于等于mid的数量
      13.        }
      14.        if (cnt >= k) {
      15.            right = mid - 1;
      16.        } else {
      17.            left = mid + 1;
      18.        }
      19.    }
      20.    return left;
      21. }
      22. };