1. int binarySearch(int[] nums, int target) {
  2.     int left = 0, right = ...;
  4.     while(...) {
  5.         int mid = left + (right - left) / 2;
  6.         if (nums[mid] == target) {
  7.             ...
  8.         } else if (nums[mid] < target) {
  9.             left = ...
  10.         } else if (nums[mid] > target) {
  11.             right = ...
  12.         }
  13.     }
  14.     return ...;
  15. }

704. 二分查找

image.png

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int left = 0;
  4.         int right = nums.length - 1;
  5.         while(left <= right){
  6.             int mid = left + (right-left)/2;
  7.             if(target > nums[mid]){
  8.                 left = mid + 1;
  9.             }else if(target < nums[mid]){
  10.                 right = mid -1;
  11.             }else{
  12.                 return mid;
  13.             }
  14.         }
  15.         return -1;
  16.     }
  17. }

33. 搜索旋转排序数组

容易考察
image.png

  1. class Solution {
  2.     /**
  3.     首选，我们选择一个mid，那么mid的两侧必然一个是有序，一个是无序的，
  4.     而判断有序那边只要看两侧端是不是左边小于右边即可
  5.     然后我们继续收左右两侧去找target
  7.     **/
  8.     public int search(int[] nums, int target) {
  9.         if(nums.length == 1){
  10.             return nums[0] == target ? 0:-1;
  11.         }
  12.         int left = 0;
  13.         int right = nums.length - 1;
  14.         while(left <= right){
  15.             int mid = left + (right - left)/2;
  16.             if(nums[mid] == target){
  17.                 return mid;
  18.             }
  19.             if(nums[0] <= nums[mid]){//左边有序
  20.                 //这里nums[mid]不能在取了，因为在上面我们已经讨论了他的情况
  21.                 if(nums[0] <= target && target < nums[mid]){//左边有序，且target就包含在里面
  22.                     right = mid - 1;//收缩右边界
  23.                 }else{
  24.                     left = mid + 1;
  25.                 }
  26.             }else{//右侧有序
  27.                 ////这里nums[mid]不能在取了，因为在上面我们已经讨论了他的情况
  28.                 if(nums[mid] < target && target <= nums[nums.length-1]){//且target就包含在里面
  29.                     left = mid + 1;
  30.                 }else{
  31.                     right = mid - 1;
  32.                 }
  33.             }
  34.         }
  35.         return -1;
  36.     }
  37. }

300. 最长递增子序列 （不会！！）

其次容易考察
image.png
首先可以用动态规划来做
dp[i] 表示是以nums[i]结尾的最长递增字串的长度
image.png

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int [nums.length];
        Arrays.fill(dp,1);//初始化数组
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j <i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

动态规划 + 二分查找
https://leetcode.cn/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/、

4. 寻找两个正序数组的中位数 困难题

image.png

69. x 的平方根

image.png

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = 0;
        while(left <= right){
            int mid = left + (right - left)/2;
            if((long)mid * mid <= x){
                 ans = mid;
                left = mid + 1;
            }else{
                right = mid -1;
            }
        }
        return ans;
    }
}

while(left <= right)的终止条件是left == right + 1，写成区间的形式就是[right + 1, right]，或者带个具体的数字进去[3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        while(left <= right){
            int mid = left + (right - left)/2;
            if((long)mid * mid < x){
                left = mid + 1;
            }else if((long)mid * mid > x){
                right = mid -1;
            }else{
                return mid;
            }
        }
        return right;
    }
}

240. 搜索二维矩阵 II

image.png
image.png
https://leetcode.cn/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-cong-you-shang-e0vj/
初始化在右上角
二分查找 - 图9
如果当前值x == target return true
如果当前值x < target 我要让x大一些，就是让这一行的i++；
如果当前值x > target 我要让x小一些，就是让这一行的j—；

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target){
            return true;
        }else if(matrix[i][j] < target){
            i++;//前进一行
        }else{
            j--;//回退一行
        }
        }

        return false;
    }
}