Binary search 归类

public class Solution {
    public static void main(String[] args) {
        int[][] matrix = {{1,5,9},{10,11,13},{12,13,15}};
        System.out.println(kthSmallest(matrix,8));
        int[] nums = {1,2,2,3,3,4,5,6};
        System.out.println(findFirstOccur(nums,3));
        System.out.println(findLastOccur(nums,1));
        System.out.println(findLargerTarget(nums,6));
        System.out.println(findSmallerTarget(nums,0));
    }
    public static int kthSmallest(int[][] matrix, int k) {
        int lo = matrix[0][0],high = matrix[matrix.length-1][matrix[0].length-1]+1;
        while(lo < high){
            int mid = (high-lo)/2 + lo;
            int count = 0 , j = matrix[0].length -1;
            for (int i=0;i<matrix.length;i++){
                while(j >= 0 && matrix[i][j] >mid ) j--;
                count += (j+1);
            }
            if (count<=k) lo = mid+1;
            else high = mid;
        }
        return lo;
    }
    public static int findFirstOccur(int[] nums,int target){//第一次出现某数的位置，没找到返回-1
        int start = 0, end = nums.length -1;
        while (start <= end){
            int mid = (end-start)/2 + start;
            if (nums[mid]>=target){
                end = mid -1;
            }else{
                start = mid + 1;
            }
        }
        return nums[start] == target? start: -1;//如果直接return start 那如果找不到就是返回应该插入的地方
    }
    public static  int findLastOccur(int[] nums,int target){//最后一次出现某数的位置，没找到返回-1
        target += 1;
        int start = 0, end = nums.length -1;
        while (start <= end){
            int mid = (end-start)/2 + start;
            if (nums[mid]>=target){
                end = mid -1;
            }else{
                start = mid + 1;
            }
        }
        return nums[end] == target-1? end: -1;
    }
    public static int findLargerTarget(int[] nums,int target){//刚好比某数大的元素位置，如果都比target小，则返回length
        target += 1;
        int start = 0, end = nums.length -1;
        while (start <= end){
            int mid = (end-start)/2 + start;
            if (nums[mid]>=target){
                end = mid -1;
            }else{
                start = mid + 1;
            }
        }
        return start;
    }

    public static int findSmallerTarget(int[] nums,int target){//刚好比某数小的元素位置，如果都比target小，则返回-1
        target += 1;
        int start = 0, end = nums.length -1;
        while (start <= end){
            int mid = (end-start)/2 + start;
            if (nums[mid]>=target){
                end = mid -1;
            }else{
                start = mid + 1;
            }
        }
        return end;
    }

}

用这个通用模板

public int findPosition(int[] nums, int target) {
        // Write your code here
        if(nums == null || nums.length == 0)
            return -1;
        int start = 0;
        int end = nums.length-1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] < target){
                start = mid;
            }
            else{
                end = mid;
            }
        }
        if(nums[start] == target)
            return start;
        if(nums[end] == target)
            return end;
        return -1;
    }