1. 只要mid满足某一个条件缩小区间到[l, mid]，最终结果l/r(包括本身) 后面的都接近于满足，mid前面的数都接近于不满足这个条件。
  2. 二分不一定要有序，只要目标值前面满足一个性质，后面不满足一个性质，我们就能找到这个值。
    理解这个就懂了二分的应用。
  3. 但是，二分对象的取值区间必须是有序的

接近于的意思：

如果ans < x，而x恰好在左端点，找出来的就是x，此时l/r 并不是ans，但它是最接近的。

二分一般对应最值问题，就是求某个值的最大或者最小，然后按照这个值慢慢逼近。

LeetCode33 旋转数组排序

方法1：

使用map来记录它原始索引和值。直接用hashMap就可以了 不需要二分

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         HashMap<Integer, Integer> hashmap = new HashMap<>();
  4.         for (int i = 0; i < nums.length; i ++)
  5.             hashmap.put(nums[i], i);
  6.         // //二分
  7.         // int l = nums[0], r = nums.length - 1;
  8.         // while(l < r){
  9.         //     int mid = (l + r) / 2;
  10.         //     if (check(mid, target)) l = mid + 1;
  11.         //     else r = mid;
  12.         // }
  13.         //装箱
  14.         Integer R = new Integer(target);
  15.         if (hashmap.containsKey(target)) return hashmap.get(target);
  16.         return -1;
  17.     }
  18. }

方法二：二分

这个数据段是非常有特点的。
怎么使用二分呢？
二分一般对应最值问题，就是求某个值的最大或者最小，然后按照这个值慢慢逼近。
前一段满足一个性质 x >= nums[0], 后一段满足x < nums[0],那么我们通过二分就能找到前一段和后一段的分界点。
分成两端来讨论。这两端都是满足一个性质的： target前面的满足nums[x] >= target。
再进行二分就可以求解了。

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         //找到分界点,要注意如果只有一个值，不会执行第一个while，返回的和实际意义不一样，所以要特别说明
  5.         if (nums.length == 1) return (nums[0] == target) ? 0 : -1;
  6.         int l = 0, r = nums.length - 1;
  7.         //这里不能使用 l = mid + 1的模板
  8.         while(l < r){
  9.             int mid = (l + r + 1) / 2;
  10.             if (nums[mid] >= nums[0]) l = mid;
  11.             else r = mid - 1;
  12.         }
  13.         if (target >= nums[0]) {
  14.             l = 0;
  15.         }else
  16.             {l = l + 1; r = nums.length - 1;}
  18.         //再次二分
  19.         while (l < r){
  20.             int mid = (l + r) / 2;
  21.             if (nums[mid] >= target) r = mid;
  22.             else l = mid + 1;
  23.         }
  24.         if(nums[r] == target) return r; 
  25.         return -1;
  26.     }
  27. }

搜索旋转排序数组 II

题目和数据都出的不行，导致有很多地方要处理细节，这里不放上来了

典型的二分题 69. 数组中数值和下标相等的元素

二分，答案res

[l, res]中index <= 元素值，(res, r]中idx > 元素值

  1. class Solution {
  2.     public int getNumberSameAsIndex(int[] nums) {
  3.         //二分，答案res [l, res]中index <= 元素值，(res, r]idx > 元素值
  4.         int l = 0, r = nums.length - 1;
  5.         if (r < 0) return -1;
  6.         while (l < r){
  7.             int mid  = l+r >> 1;
  8.             if (mid <= nums[mid]) r = mid;
  9.             else l = mid + 1;
  10.         }
  11.         if (l != nums[l]) return -1;
  12.         return l;
  13.     }
  14. }

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

类似，特别处理一下升序数组

  1. class Solution {
  2.     public int findMin(int[] nums) {
  3.         int l = 0, r = nums.length - 1;
  4.         if (nums.length == 1 || nums[r] > nums[l]) return nums[0];
  5.         //这里不能使用 l = mid + 1的模板
  6.         while(l < r){
  7.             int mid = (l + r + 1) / 2;
  8.             if (nums[mid] >= nums[0]) l = mid;
  9.             else r = mid - 1;
  10.         }
  11.         return nums[r + 1];
  12.     }
  13. }

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

把重复的元素先删除

  1. class Solution {
  2.     public int findMin(int[] nums) {
  3.         //找到分界点,要注意如果只有一个值，不会执行第一个while，返回的和实际意义不一样，所以要特别说明
  4.         int l = 0, r = nums.length - 1;
  5.         if (nums.length == 1 || nums[r] > nums[l]) return nums[0];
  7.         while(r >= 0 && nums[r] == nums[0]) r--;
  8.         if (r < 0) return nums[0];
  10.         //这里不能使用 l = mid + 1的模板
  11.         while(l < r){
  12.             int mid = (l + r + 1) / 2;
  13.             if (nums[mid] >= nums[0]) l = mid;
  14.             else r = mid - 1;
  15.         }
  16.         return nums[r + 1];
  17.     }
  18. }

LC162. 寻找峰值

二分

如果mid < nums[mid + 1] 右边一定有峰值， 如果mid > nums[mid + 1] 包括mid左边一定有峰值。
这样就划分了mid前后两个区间。

代码

  1. class Solution {
  2.     public int findPeakElement(int[] nums) {
  3.         //如果mid < nums[mid + 1] 右边一定有峰值， 如果mid > nums[mid + 1] 包括mid左边一定有峰值
  4.         //这就满足了二分的基本思想
  5.         int l = 0, r = nums.length - 1;
  6.         if (l == r) return 0;
  7.         while (l < r){
  8.             int mid = (l + r) / 2;
  9.             if (nums[mid] > nums[mid + 1]) r = mid;
  10.             else l = mid + 1;
  11.         }
  12.         return r;
  13.     }
  15. }

275. H 指数 II

解题思路

这道题的难点在于找到一个点，这个点前后的性质不同。
我们来看，假设二分区间为[0, len - 1]假设一个index为下标，index之后都满足citations[index] >= len - index 这个特点。index之前都满足len - index >= citations[index]的性质。
因此使用二分。
二分 - 图1

代码

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

双指针+二分378. 有序矩阵中第 K 小的元素

解题思路

二分: [amin, mid] <= mid 的个数 <= k , [mid + 1, amax]中，<= mid的个数>=k
根据数组的性质，使用双指针算法
从0行末端开始，遇到<= mid 就加上当前行的元素个数。又因为列递增，只需要考虑下行同列的元素<=mid.这样列指针就是一直向左的。相当于遍历一遍。O(N+M)= o(n)
总复杂度O(n * LOGN)

代码

  1. class Solution {
  2.     public int kthSmallest(int[][] matrix, int k) {
  3.         //二分: [amin, ans] <= ans 的个数 <= k , [ans + 1, amax]中，<= ans个数>=k
  4.         //双指针求是否<=ans的个数
  5.         int m = matrix.length, n = matrix[0].length;
  6.         int l = matrix[0][0], r = matrix[m - 1][n - 1];
  7.         while (l < r)
  8.         {
  9.             //要去k的左端点不能是右端点，因为<= x的个数，x的取值[matrix[index], matrix[index + 1])
  10.             //index为答案的下标
  11.             int mid = (l + r) / 2;
  12.             if(get(mid, matrix) >= k)r = mid;
  13.             else l = mid + 1;
  14.         }
  15.         return r;
  16.     }
  17.     public int get(int mid, int[][] matrix){
  18.         int res = 0;
  19.         for (int i = 0, j = matrix[0].length - 1; i < matrix.length; i ++)
  20.         {
  21.             while(j >= 0 && matrix[i][j] > mid)j--;
  22.             res += j + 1;
  23.         }
  24.         return res;
  25.     }
  26. }

双指针+二分LC668. 乘法表中第k小的数

解题思路

经典的二分+双指针
根据乘法表的规律可以使用双指针求<= x 的个数
同时<=x 的个数 >= k的时候，进入到左区间。反之进入右区间
最后就是找出了一个最小的x，使得<=x的个数 <= k,x就是第k个最小的数。

注意一点：一定是<k进入右区间， <=k 进入右区间找出来的是 最大的x（<=x的个数 <= k），乘法表中不一定存在。

代码

  1. class Solution {
  2.     public int findKthNumber(int m, int n, int k) {
  3.         //<=mid的个数>=k r = mid ，找最小的mid
  4.         //打表会爆内存
  5.         int l = 1, r = 1;
  6.         r = m * n;
  7.         //System.out.println(r);
  8.         while (l < r){
  9.             int mid = (l + r) / 2;
  10.             int res = 0;
  11.             for (int i = 0, j = n - 1; i < m; i ++){
  12.                 while (j >= 0 && (i + 1) * (j + 1) > mid)j --;
  13.                 res += j + 1;
  14.             }
  15.             if (res >= k) r = mid;
  16.             else l = mid + 1;
  17.         }
  18.         return l;
  19.     }
  20. }

二分性质LeetCode719 找出第 k 小的距离对

解题思路

定义最小距离是mid，那么当第k个最小数对的距离为mid时，满足<=mid的数对个数<=k符合二分的思想
同时使用双指针求出<=某一距离的数对的个数,前提是nums数组有序。

  1.  for(int i = 0, j = 0; i < nums.length; i ++)
  2. {
  3.     while(nums[i] - nums[j] > mid) j++;
  4.     res += i - j;
  5. }

注意我们要求第k个最小数对，也就是找到k的左边界点。
if(res >= k)r = mid 找的才是左边界点。

代码

  1. class Solution {
  2.     public int smallestDistancePair(int[] nums, int k) {
  3.         //定义第k个最小距离是mid，那么<=mid的数对个数<=k, >mid的数对个数>k
  4.         //通过二分就能找到最小数对了
  5.         //如何求<= mid 的距离对数有多少个? 使用双指针
  6.         //直接构造最小距离数组会超时
  7.         int m = nums.length;
  8.         Arrays.sort(nums);
  9.         int l = 0, r = 0;
  10.         for (int i = 0; i < m; i ++)
  11.         {
  12.             r = Math.max(r, nums[i]);
  13.         }
  14.         while (l < r){
  15.             int mid = (l + r) / 2;
  16.             if (check(mid,nums ,k)) r = mid;
  17.             else l = mid + 1;
  18.         }
  19.         return r;
  20.     }
  22.     public boolean check(int mid,int[] nums ,int k){
  23.         //如何求<= mid 的距离对数有多少个? 使用双指针
  24.         int res = 0;
  25.         for(int i = 0, j = 0; i < nums.length; i ++)
  26.         {
  27.             while(nums[i] - nums[j] > mid) j++;
  28.             res += i - j;
  29.         }
  30.         if (res >= k) return true;
  31.         else return false;
  32.     }
  33. }

二分性质 14. 不修改数组找出重复的数字 - AcWing题库

思路

我们能找到一个性质，根据这个性质，能把情况一分为二。

找到一个数n，让数组中满足数属于1~n区间的个数分为 <= n 和 > n两种情况。

<= n表示数组中有重复的数字。因此当区间为1的时候，就是对应的重复数字。

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

二分性质 68. 0到n-1中缺失的数字

从 二分 - 图2中二分mid，如果[l, mid]中元素在数组中的个数 < mid - l + 1,说明缺失的元素在这个区间中

使用hashSet存放，用来判断元素是否在数组中。

  1. class Solution {
  2.     public int getMissingNumber(int[] nums) {
  3.         //从 0~n-1中二分mid，如果[l, mid]中元素在数组中的个数 < mid - l + 1,说明缺失的元素在这个区间中
  4.         HashSet<Integer> hash = new HashSet<Integer>();
  5.         int l = 0, r= nums.length;
  6.         if (l == r)return 0;
  7.         for (int i = l; i < r; i ++)
  8.             hash.add(nums[i]);
  9.         while (l < r){
  10.             int mid = l + r >> 1;
  11.             int num = 0, len = 0;
  12.             for (int i = l; i <= mid; i ++){
  13.                 if (hash.contains(i))
  14.                     len++;
  15.             }
  16.             num += len;
  17.             if (num < mid - l + 1) r = mid;
  18.             else l = mid + 1;
  19.         }
  20.         return l;
  21.     }
  22. }