一.题目

1.旋转数组

思路：旋转数组的思路都是使用mid把数组分成两半[slow, mid], [mid, high]，通过判断有一半是有序的，然后判断target是否在该有序数组中来丢弃一半到达缩小搜索空间的目的.
注意：搜索的目标target可能不存在.

LeetCode-33.搜索旋转排序数组

描述：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
例子
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
思路
无重复值的旋转数组，先判断出被mid分开的有序的哪一半，然后和target比较排除一半
循环条件是low<=high，并不会导致死循环的原因：

  • 当low等于high时, mid等于low,这时可能nums[mid]等于target就直接返回
  • 否则[low, mid]会认为是升序, 而target一定不在该区间, 所以 low = mid+1,所以循环终止
    1.   // 选择出被mid分开的有序的哪一半, 然后和target比较丢弃掉一半
    2.   public int search(int[] nums, int target) {
    3.       if(nums==null || nums.length==0){
    4.           return -1;
    5.       }
    6.       int low = 0, high = nums.length - 1;
    7.       // 就算区间里只有一个元素,也是有可能为target
    8.       while(low<=high){
    9.           int mid = (high - low)/2 + low;
    10.           if(nums[mid] == target){
    11.               return mid;
    12.           }
    13.           // 如果[low, mid]升序(low可能等于mid),
    14.           if(nums[low] <= nums[mid]){
    15.               // 如果target在升序区间, 扔掉另一半
    16.               if(nums[low]<=target && target<= nums[mid]){
    17.                   high = mid;
    18.               }else{
    19.                   low = mid + 1;
    20.               }
    21.           // 若[mid, high]升序    
    22.           }else{
    23.               // 如果target在升序区间, 扔掉另一半
    24.               if(nums[mid]<=target && target<= nums[high]){
    25.                   low = mid;
    26.               }else{
    27.                   high = mid - 1;
    28.               }
    29.           }
    30.       }
    31.       return -1;
    32.   }

    LeetCode-81. 搜索旋转排序数组 II

    描述：类似于leetcode-33，但是输入的旋转数组可能有重复值，判断给定的目标值是否存在于数组中，若存在返回 true，否则返回 false。
    例子
    输入: nums = [2,5,6,0,0,1,2], target = 0
    输出: true
    思路：因为有重复数
    （1）特殊case，比如10111 和 11101 这种，如果nums[mid]为1，而左右两端都是1，这时无法判断[low, mid]有序还是[mid, high]有序，此时 low++ 即可。相当于去掉一个重复的干扰项
    （2）正常case，两端不相等，比如2 3 4 5 6 7 1 或6 7 1 2 3 4 5这种，就可以判断出一个有序然后丢弃一半来缩小搜索空间了
    注意：如果重复值太多，那么每次搜索空间的大小就是1，那么就会退化为O(n)的遍历。
    1.   // 两端相等时无法判断哪一半有序, 左右两端相等时右移 low 一位
    2.   // 两端不相等时, 判断出有序区间, 然后丢弃点一半区间
    3.   public boolean search(int[] nums, int target) {
    4.       if(nums == null || nums.length==0){
    5.           return false;
    6.       }
    7.       int low = 0, high = nums.length-1;
    8.       // 搜索特定target是否存在的循环条件low<=high,因为只剩一个值也可能就是target
    9.       while(low<=high){
    10.           int mid = (high - low)/2 + low;
    11.           if(nums[mid] == target){
    12.               return true;
    13.           }
    14.           // 两端相等无法判断哪一半有序, low++
    15.           // 有重复数独有判断
    16.           if(nums[low] == nums[high]){
    17.               low++;
    18.               continue;
    19.           }
    20.           // 下面为无重复数旋转数组逻辑
    21.           // [low, mid]为升序
    22.           if(nums[low]<=nums[mid]){
    23.               if(nums[low]<=target && target<=nums[mid]){
    24.                   // target在升序区间内
    25.                   high = mid;
    26.               }else{
    27.                   // target不在升序区间内
    28.                   low = mid+1;
    29.               }
    30.           // [mid, high]为升序    
    31.           }else{
    32.               if(nums[mid]<=target && target<=nums[high]){
    33.                   // target在升序区间内
    34.                   low = mid;
    35.               }else{
    36.                   // target不在升序区间内
    37.                   high = mid-1;
    38.               }
    39.           }
    40.       }
    41.       return false;
    42.   }

    LeetCode-153. 寻找旋转排序数组中的最小值

    描述：对无重复数的旋转数组，请找出其中最小的元素。
    例子1
    输入：nums = [3,4,5,1,2]
    输出：1
    例子2
    输入：nums = [4,5,6,7,0,1,2]
    输出：0
    思路
    情况1：数组没有旋转，最左端元素就是最小值
    nums[low]情况2：[3, 4, 5, 1, 2] 会发现最小值是从左到右升序的一个下降点.
    当nums[low]>nums[high]时，就是至少有一个数发生了旋转（所有数都旋转等于没有数旋转）
    若[low, mid]有序，则最小值在[mid+1, high]区间
    若[mid, high]有序，则最小值在[low, mid]区间(mid 有可能为最小值)
    循环条件为low不会死循环，当区间长度为2时比如[2, 1]时, mid会等于low, 那么 low会增加1，导致区间长度为1
    1.   // 若[low, mid]有序，则最小值在[mid+1, high]区间
    2.   // 若[mid, high]有序，则最小值在[low, mid]区间(mid 有可能为最小值)
    3.   // 注意数组可能没有旋转
    4.   public int findMin(int[] nums) {
    5.       if(nums.length==1){
    6.           return nums[0];
    7.       }
    8.       int low = 0, high = nums.length - 1;
    9.       // 如果只剩一个元素,那么必然是最小的元素
    10.       while(low<high){
    11.           // 数组没有旋转
    12.           if(nums[low]< nums[high]){
    13.               return nums[low];
    14.           }
    15.           int mid = (high - low)/2 + low;
    16.           // 若[low ,mid]有序
    17.           if(nums[low]<=nums[mid]){
    18.               low = mid+1;
    19.           // 若[mid, high]有序    
    20.           }else{
    21.               high = mid;
    22.           }
    23.       }
    24.       return nums[low];
    25.   }

    2.数学运算

    溢出问题：
    牵涉到int型的数学运算，都要注意溢出的问题
    因为计算机存储补码，Integer.MIN_VALUE的相反数会溢出

    leetcode-29.两数相除

    描述：计算两个数的商，不能使用除法、乘法、mod运算。
    思路
    公式 divide >= divisor 2^n，找到最大的n，则2^n就是商，1<<如何找到最大的n：如何表示divisor2^n，将divisor自加，自加一次为divisor2^1,自加两次为divisor2^2
    定义f(x ,y)为x除以y的商
    例如f(11, 3)，11>3所以商至少为1(2^0)，将3自加为6，11>6所以商至少为2(2^1)，再次将6自加为12），11<12，所以商小于4(2^2)，f(11, 3) = 2 = f(11-6, 3)。
  1.     // 使用负数来运算,规避Integer.MIN_VALUE转化为正数溢出的问题
  2.     // 负数自加也有溢出问题, 当负数溢出时不再小于0
  3.     public int divide(int dividend, int divisor) {
  4.         if(dividend == 0){
  5.             return 0;
  6.         }
  7.         if(divisor==1){
  8.             return dividend;
  9.         }
  10.         if(divisor == -1){
  11.             return dividend==Integer.MIN_VALUE?Integer.MAX_VALUE:(-dividend);
  12.         }
  13.         // flag为false表示结果为负数
  14.         boolean flag = true;
  15.         if((dividend<0 && divisor>0) || (dividend>0 && divisor<0)){
  16.             flag = false;
  17.         }
  18.         dividend = dividend<0?dividend:(-dividend);
  19.         divisor = divisor<0?divisor:(-divisor);
  20.         int res = div(dividend, divisor);
  21.         return flag?res:(-res);
  22.     }
  24.     // 用负数进行计算
  25.     public int div(int divide, int divisor){
  26.         if(divide > divisor){
  27.             return 0;
  28.         }
  29.         int count = 0 ;
  30.         int temp = divisor;
  31.         // 有没有溢出,若temp溢出,那么temp不再小于0
  32.         while((temp+temp)<0 && (temp+temp)>=divide){
  33.             count++;
  34.             temp += temp;
  35.         }
  36.         count = 1<<count;
  37.         return count + div(divide - temp, divisor);
  38.     }

leetcode-50.Pow(x, n)

思路
快速幂乘法
指数减少一半，底数自乘一次，指数为奇数时，结果乘一次底数
（1）迭代

  1.     //  快速幂乘法:指数减少一半, 底数自乘, 指数为奇数时结果乘以指数
  2.     //  n为负数时将n变为正数可能溢出, 用long型保存n
  3.     public double myPow(double x, int n) {
  4.         if(n==0){
  5.             return 1;
  6.         }
  7.         if(x==0){
  8.             return 0;
  9.         }
  10.         double base = x;
  11.         double res = 1;
  12.         long newN = n;
  13.         if(newN<0){
  14.             base = 1/base;
  15.             newN = - newN;
  16.         }
  17.         while(newN>0){
  18.             if((newN&1)==1){
  19.                 res *= base;
  20.             }
  21.             base *= base;
  22.             newN = newN>>>1;
  23.         }
  24.         return res;
  25.     }

（2）递归

  1.     // 指数减小一半, 底数自乘, 指数为奇数时结果乘以一个底数
  2.     // n为Integer.MIN_VALUE时相反数溢出
  3.     public double myPow(double x, int n) {
  4.         if(n==0){
  5.             return 1;
  6.         }
  7.         if(n==1){
  8.             return x;
  9.         }
  10.         if(n==-1){
  11.             return 1/x;
  12.         }
  13.         long newN = n;
  14.         if(newN<0){
  15.             x = 1/x;
  16.             newN = -newN;
  17.         }
  18.         return pow(x, newN);
  19.     }
  20.     public double pow(double x, long n){
  21.         if(n==1){
  22.             return x;
  23.         }
  24.         if(n%2==1){
  25.             return x*pow(x, n-1);
  26.         }
  27.         return pow(x*x, n/2);
  28.     }

3.矩阵二分

LeetCode-74.搜索二维矩阵

描述：判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

例子：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
思路：

  1.     // 按照每行从左到右、从第一行到最后一行的顺序得到的数字序列就是一个升序序列
  2.     // 对区间二分
  3.     // 每一个mid都是 index, 换算为对应row、column的index=> row = mid/n, column = mid%n
  4.     public boolean searchMatrix(int[][] matrix, int target) {
  5.         int m = matrix.length, n = matrix[0].length;
  6.         int low = 0, high = m*n-1;
  7.         while(low<=high){
  8.             int mid = (high-low)/2 + low;
  9.             int val = matrix[mid/n][mid%n];
  10.             if(val==target){
  11.                 return true;
  12.             }else if(val<target){
  13.                 low = mid + 1;
  14.             }else{
  15.                 high = mid - 1;
  16.             }
  17.         }
  18.         return false;
  19.     }

LeetCode-240.搜索二维矩阵II

描述：搜索 _m_ x _n_ 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

例子：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
思路：

  1.     // 从右上角出发, 大于该元素则向下移动, 小于该元素向左移动
  2.     public boolean searchMatrix(int[][] matrix, int target) {
  3.         int m = matrix.length, n = matrix[0].length;
  4.         int x = 0, y = n-1;
  5.         while(x<m && y>=0){
  6.             if(matrix[x][y] == target){
  7.                 return true;
  8.             }else if(matrix[x][y] < target){
  9.                 x++;
  10.             }else{
  11.                 y--;
  12.             }
  13.         }
  14.         return false;
  15.     }

LeetCode-378.有序矩阵中第K小的元素

描述：给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
本质上来来说，这个矩阵是n个排序数组
思路：
（1）对所有元素排序，遍历到第k个元素，2-4 二分搜索BinarySearch - 图1
（2）堆+归并
归并 k 个链表的思路
维护一个大小为n的小根堆heap，小根堆里放的是这n行元素中还没有被归并的从左到右第一个元素（最小的元素），每次从堆里拿出最小值，然后从这个最小值所在数组拿出后面一个元素放进堆，只需要k次就可以找到第k小的值
时间O(KlogN)，最坏情况下2-4 二分搜索BinarySearch - 图2，因为 k 可能为2-4 二分搜索BinarySearch - 图3

  1.     // 借鉴归并 k 个链表, 把每个链表的还未归并的元素中的最小值放到一个堆中
  2.     // 得到第 i 个最小值 O(logN), 一共k次 O(KlogN)
  3.     public int kthSmallest(int[][] matrix, int k) {
  4.         // 数组 "0位置" 保存 "key", "1位置" 保存 "行index", "2位置" 保存 "列index"
  5.         PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->a[0]-b[0]);
  6.         int n = matrix.length;
  7.         for(int i=0;i<n;i++){
  8.             queue.add(new int[]{matrix[i][0], i, 0});
  9.         }
  10.         int res = 0;
  11.         // 每次poll和push操作O(logN), 一共k次
  12.         for(int i=0;i<k;i++){
  13.             int[] val = queue.poll();
  14.             res = val[0];
  15.             // 每次poll出来的最小值, 下一个最小值一定是该最小值所在行的右边一个(如果右边还有的话)
  16.             if(val[2]!=n-1){
  17.                 int row = val[1];
  18.                 int column = val[2];
  19.                 queue.add(new int[]{matrix[row][column+1], row, column+1});
  20.             }
  21.         }
  22.         return res;
  23.     }

4.对值范围二分

LeetCode-222.完全二叉树的节点个数

LeetCode-287.寻找重复数

LeetCode-378.有序矩阵中第K小的元素

思路： 二分查找
矩阵左上角元素值最小为min，右下角元素值最大为max，所以矩阵值范围是[min, max]，对值进行二分搜索
每次得到中间值mid，搜索矩阵中小于等于mid元素的元素个数x
统计小于等于mid元素的方法为从左下角元素(x, y)出发，如果该元素小于等于mid则累计加x+1，然后 右移动
否则下移动。
若 x 若x>=mid ，则答案在[min, mid]
夹逼得到第k小元素

  1.     // 对值进行二分,二分次数O(log(max-min))
  2.     public int kthSmallest(int[][] matrix, int k) {
  3.         int n = matrix.length;
  4.         int low = matrix[0][0];
  5.         int high = matrix[n-1][n-1];
  6.         // 不会死循环,每次 low或high都在缩小
  7.         while(low<high){
  8.             int mid = (high - low)/2 + low;
  9.             int number = countLessThanTarget(matrix, mid);
  10.             if(number<k){
  11.                 low = mid+1;
  12.             }else{
  13.                 high = mid;
  14.             }
  15.         }
  16.         return low;
  17.     }
  18.     // 每次调用 O(logN)
  19.     public int countLessThanTarget(int[][] matrix, int target){
  20.         int n = matrix.length;
  21.         int res = 0;
  22.         int x = n-1, y = 0;
  23.         while(x>=0 && y<n){
  24.             if(matrix[x][y]<=target){
  25.                 res += x+1;
  26.                 y++;
  27.             }else{
  28.                 x--;
  29.             }
  30.         }
  31.         return res;
  32.     }

5.变形二分查找

LeetCode-162. 寻找峰值

描述：
Input:
Output:
思路：

LeetCode-209. 长度最小的子数组

描述： 给定一个含有 n 个正整数的数组和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0
例子：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
思路：
（1）暴力：枚举所有可能的起点O(N)，对每个起点start需要O(N)找到合适的end，总共O(NN)
（2）前缀数组 + 二分
“连续子数组和” 联系到前缀数组可以以O(1)求任意区间[i, j]的和
因为输入数组nums的所有元素为正，所以前缀数组是递增的
*”在递增数组中寻找target” 使用二分
数组nums 在区间[i, j]的和为：
i>0时，prefix[j] - prefix[i]
i=0时，prefix[j]

  1.     // 前缀数组 + 二分
  2.     // 前缀数组prefix[i] 表示数组nums从nums[0]累加到nums[i]
  3.     // 数组nums在区间[i,j]的累加和为prefix[j]-prefix[i-1], i为0时为prefix[j]
  4.     public int minSubArrayLen(int target, int[] nums) {
  5.         int[] prefix = new int[nums.length];
  6.         int n = nums.length;
  7.         int sum = 0;
  8.         for(int i=0;i<n;i++){
  9.             sum += nums[i];
  10.             prefix[i] = sum;
  11.         }
  12.         int minLen = Integer.MAX_VALUE;
  13.         for(int i=0;i<n;i++){
  14.             int end = binary(prefix, nums, i, target);
  15.             if(end>=0 && end<n){
  16.                 minLen = Math.min(minLen, end - i + 1);
  17.             }
  18.         }
  19.         return minLen!=Integer.MAX_VALUE?minLen:0;
  20.     }
  21.     // 找到从start开始的累积和大于等于target的最小区间
  22.     // prefix[1,2,2], target = 10时, 找不到合法的end, end会上溢出
  23.     // prefix[5,6,7],target = 4时, high会下溢出, 但low=0合法
  24.     public int binary(int[] prefix, int[] nums, int start, int target){
  25.         int low = start, high = prefix.length-1;
  26.         while(low<=high){
  27.             int mid = (low+high)>>>1;
  28.             int sum = 0;
  29.             // 计算累积和
  30.             if(start!=0){
  31.                 sum = prefix[mid]- prefix[start-1];
  32.             }else{
  33.                 sum = prefix[mid];
  34.             }
  35.             if(sum==target){
  36.                 return mid;
  37.             }else if(sum<target){
  38.                 low = mid + 1;
  39.             }else{
  40.                 high = mid - 1;
  41.             }
  42.         }
  43.         return low;
  44.     }

（3）滑动窗口

  1.     // 滑动窗口
  2.     // right向右滑动开大窗口
  3.     // left向右滑动缩小窗口
  4.     // 符合条件的子序列更新全局最小子序列长度
  5.     public int minSubArrayLen(int target, int[] nums) {
  6.         int minLen = Integer.MAX_VALUE;
  7.         int left = 0, right = 0;
  8.         int sum = 0;
  9.         // 开右窗口
  10.         while(right<nums.length){
  11.             sum += nums[right];
  12.             // 缩左窗口
  13.             while(sum>=target){
  14.                 minLen = Math.min(minLen, right - left + 1);
  15.                 sum -= nums[left];
  16.                 left++;
  17.             }
  18.             right++;
  19.         }
  20.         return minLen!=Integer.MAX_VALUE?minLen:0;
  21.     }

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

LeetCode-230.二叉搜索树中第K小的元素

LeetCode-275.H指数II

LeetCode-300.最长递增子序列

LeetCode-436.寻找右区间

LeetCode-454.四数相加I

LeetCode-475.供暖器

LeetCode-497.非重叠矩形中的随机点

二.总结

1.变形二分查找可能无有效结果

结论：对于非 “在有序数组中寻找某个特定target的” 二分查找，都要注意可能没有有效的输入结果。
原因：

  • 因为查找等于特定target的二分程序，只有两种情况（1）循环找到target返回true（2）循环外直接返回false
  • 非查找等于target的变形二分”是通过特殊的判断，最后返回low或high来间接得到答案

验证是否合法：对于这类二分，必须使用题目的额外条件来验证的得到的目标下标 low或high是否满足条件
例子1：LeetCode-275.H 指数 II
思想：左右夹逼找到”最大的h指数”的下标i =>h指数=n-i，但是这个i可能不是有效的，比如当输入为[0, 0, 0]时二分查找最后会得到i=n-1, 但是其实是无效的
无效的情况：

  • 验证得到的下标i，citations[i]>=n-i则说明i有效

例子2：LeetCode-34.在排序数组中查找元素的第一个和最后一个位置
找到第一个的思想：找到了一个target也要继续向左找，所以搜索范围向左偏：high = mid - 1，最后low位置可能是结果
找到最后一个的思想：找到了一个target也要继续向右找，所以搜索范围向右偏：low = mid -1，最后high位置可能是结果
无效的情况：

  • 当输入为[0 , 1 ,3, 5]，target = 2时，最后返回的low会停在index=2，high会停在index=1，所以返回的low或high都是非有效的
  • 输入为[0,1,2,3] 查找 5时，查找第一个5时返回的low会上溢出为n=4
  • 输入[5, 6, 7]查找最后一个1时返回的high会下溢出为-1