Binary Search

Binary Search 解题模板
https://leetcode.com/articles/introduction-to-binary-search/

注意：需要考虑数组里是否有重复值

//check if the array is valid
if(nums==null||nums.length==0) return result;

//check if the matrix is valid
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false;

34. Search for a Range

https://leetcode.com/problems/search-for-a-range/description/
思路：先找左边界，再找右边界
注意：target=nums[mid]时的处理方法不同；给startpoint和endpoint赋值时判断left和right的顺序不同。

  public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums==null||nums.length==0) return result;
        int startpoint, endpoint;
        int left=0, right=nums.length-1, mid;
        //find start position, when target=nums[mid], right position come down
        while(left+1<right){
            mid=left+(right-left)/2;
            if(target>nums[mid]){
                left=mid;
            }else right=mid;
        }
        if(target==nums[left]) startpoint=left;
        else if(target==nums[right]) startpoint=right;
        else return result;
        
        //find end position, when target=nums[mid], left position come up
        left=0;
        right=nums.length-1;
        while(left+1<right){
            mid=left+(right-left)/2;
            if(target<nums[mid]){
                right=mid;
            }else left=mid;
        }
        //judge right range first
        if(target==nums[right]) endpoint=right;
        else endpoint=left;
        
        result[0]=startpoint;
        result[1]=endpoint;
        return result;
    }

162. Find Peak Element

思路: You may imagine that nums[-1] = nums[n] = -∞.
如果中间值不是峰值，那么在比它大的临近数一侧一定有峰值。

1. mid是峰值：
   [2 3 3]
2. mid不是峰值：
   [2 3 4] -> left=mid
   [4 3 2] -> right=mid

  public int findPeakElement(int[] nums) {
        int left=0, right=nums.length-1, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]) return mid;
            if(nums[mid]<nums[mid+1]) left=mid;
            else right=mid;
        }
        if(nums[left]>nums[right]) return left;
        else return right;
  }

35. Search Insert Position

1. target在数组中
   [1, 2, 3, 4] 2
2. target不在数组中，target比数组中最大的数小，比最小的数大
   [1, 2, 4] 2
3. target不在数组中，target比数组中最大的数大
4. target不在数组中，target比数组中最小的数小
   注意：left+1<right时，考虑数组长度是2的情况。

  public int searchInsert(int[] nums, int target) {
        if(nums.length==0) return 0;
        int left=0, right=nums.length-1, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            if(nums[mid]<target) left=mid;
            else right=mid;  
        }
        if(nums[right]<target) return right+1;  
        else if(nums[left]>=target) return left; 
        else return right; 
  }

744. Find Smallest Letter Greater Than Target

duplicated sorted array, like ["e","e","e","e","e","e","n","n","n","n"]，当target=letters[mid]时，注意应该让left=mid还是right=mid。
在这道题里，如果让left=mid， ["e","e","e","e","e","e","n","n","n","n"]，最后left和right指向最左边，找不到比e大的元素是谁。

    public char nextGreatestLetter(char[] letters, char target) {
        int left=0, right=letters.length-1, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            //judge when target=letters[mid]
            if(target>=letters[mid]){
                left=mid;
            }else right=mid;
        }
        if(target>=letters[right]||target<letters[left]){
            return letters[0];
        }else return letters[right];
    }

[349] Intersection of Two Arrays

[350] Intersection of Two Arrays II

[441] Arranging Coins

累加求和公式：sum = (1+x)*x/2

    public int arrangeCoins(int n) {
        if(n==0||n==1) return n;
        int left=1, right=n, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            //mid的类型一定要是long
            long multi = (long)mid*(mid+1)/2;
            if(multi<=n) left=mid;
            else right=mid;
        }
        return left;
    }

[367] Valid Perfect Square (pass)

class Solution {
    public boolean isPerfectSquare(int num) {
        int left=0, right=num, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            long result=(long)mid*mid;
            if(result<=num) left=mid;
            else right=mid;
        }
        if(left*left==num || (long)right*right==num) return true;
        else return false;
    }
}

[287] Find the Duplicate Number

解法一：O(NlogN)
抽屉原理，以index作为mid标准，遍历数组计算有多少<=mid的元素，移动left和right指针。

class Solution {
    public int findDuplicate(int[] nums) {
        int left=0, right=nums.length-1, mid, n;
        while(left+1<right){
            for(int i=0; i<nums.length-1; i++){
                if(nums[i]<=mid) n++;
            }
            if(n<=mid) left=mid;
            else right=mid;
        }
        return right;
    }
}

解法二：（待补充）Linked-List

33. Search in Rotated Sorted Array

no duplicate

1. [4 5 6 7 0 1 2] left<mid
   target=4: target在左边范围内，right=mid
   target=2: target在右边范围内，left=mid
2. [5 6 7 0 1 2 4] left>mid
   target=4: target在右边范围内，left=mid
   target=2: target在左边范围内， right=mid

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0) return -1;
        int left=0, right=nums.length-1, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            //left<mid
            if(nums[left]<nums[mid]){
                if(nums[left]<=target && nums[mid]>=target) right=mid;
                else left=mid;
            //left>mid
            }else{
                if(nums[right]>=target && nums[mid]<target) left=mid;
                else right=mid;
            }
        }
        if(nums[right]==target) return right;
        else if(nums[left]==target) return left;
        else return -1;
    }
}

[81] Search in Rotated Sorted Array II

1. [2 2 5 6 0 0 1] left<mid
   target=2: target在左边，right=mid
   target=1: target在右边，left=mid
2. [2 5 6 0 0 1 2] left>mid
   target=2: target在右边，left=mid
   target=1: target在左边，right=mid
3. [2 3 5 2 2 2 2] left=mid
   left++ (不知道怎么想出来这一步的)

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums==null||nums.length==0) return false;
        int left=0, right=nums.length-1, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            if(nums[left]<nums[mid]){
                if(target>=nums[left] && target<=nums[mid]) right=mid;
                else left=mid;
            }else if(nums[left]>nums[mid]){
                if(target>nums[mid] && target<=nums[right]) left=mid;
                else right=mid;
            }else{
                left++;
            }
        }
        if(nums[left]==target || nums[right]==target) return true;
        else return false;
    }
}

153. Find Minimum in Rotated Sorted Array

no duplicate
left<right return left 最左小于最右时，数组没有旋转过，最小值是最左边。

1. mid>left mid>right
   [4 5 6 7 0 1 2] mid>mid-1 mid>mid+1 left=mid
   [2 4 5 6 7 0 1] mid>mid-1 mid<mid+1 left=mid
2. mid>left mid<right
   [0 1 2 4 5 6 7] right=mid
3. mid<left mid<right
   [5 6 7 0 1 2 4]
   [6 7 0 1 2 4 5]
   right=mid;

class Solution {
    public int findMin(int[] nums) {
        int left=0, right=nums.length-1, mid;
        if(nums[left]<nums[right]) return nums[left];
        while(left+1<right){
            mid=left+(right-left)/2;
            //第一种情况
            if(nums[mid]>nums[left] && nums[mid]>nums[right]) left=mid; 
            //剩下两种情况
            else right=mid;
        }
        if(nums[left]<nums[right]) return nums[left];
        else return nums[right];
    }
}

154. Find Minimum in Rotated Sorted Array II

have duplicate
多了一种情况：left=mid left++

class Solution {
    public int findMin(int[] nums) {
        int left=0, right=nums.length-1, mid;
        if(nums[left]<nums[right]) return nums[left];
        while(left+1<right){
            mid=left+(right-left)/2;
            //第一种情况
            if(nums[mid]>nums[left] && nums[mid]>nums[right]) left=mid; 
            //多出来的那种情况
            else if(nums[mid]==nums[left]) left++;
            //剩下两种情况
            else right=mid;
        }
        if(nums[left]<nums[right]) return nums[left];
        else return nums[right];
    }
}

[378] Kth Smallest Element in a Sorted Matrix （重做）

java matrix

public static void main(String[] args) {  
    int[][] A=new  int[][]{{1,2},{4,5},{7,8,10,11,12},{}};  
    System.out.println(A.length);//4,表示数组的行数  
    System.out.println(A[0].length);//2，表示对应行的长度  
    System.out.println(A[1].length);//2  
    System.out.println(A[2].length);//5  
}  

因为这个矩阵没有按照从小到大的顺序，所以不能按照index来做二分。
用数值大小的中间值做二分。
思路：这种不以矩阵内数字划分的问题最好用left<right来做

[74] Search a 2D Matrix

log(M*N)=logM+logN 直接当成一个array来找即可。

class Solution {
    //O(log(M*N))
    public boolean searchMatrix(int[][] matrix, int target) {
        //check if the matrix is valid
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false;
        int row=matrix.length;
        int col=matrix[0].length;
        int left=0, right=row*col-1, mid;
        while(left+1<right){
            mid=left+(right-left)/2;
            if(target<matrix[mid/col][mid%col]) right=mid;
            else left=mid;
        }
        return (target==matrix[left/col][left%col] || target==matrix[right/col][right%col]);
    }
}

240. Search a 2D Matrix II

1. binary search
   思路：找特征点，左下角和右上角两个点，以左下角的点为例，比它大的数都在右边，比它小的数都在它上边。
   参考：https://zhuanlan.zhihu.com/p/29555088
   O((m²⁺ⁿ2)^1/2)

// runtime: 16ms
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0||matrix[0]==null||matrix[0].length==0) return false;
        int m=matrix.length-1, n=0, divide;
        while(m>=0 && n<=matrix[0].length-1){
            divide=matrix[m][n];
            if(divide==target) return true;
            else if(divide<target) n++;
            else m--;  
        }
        return false;
    }
}