Leetcode系列：二分查找

35. 搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {

        int len = nums.length;
        if(target<nums[0]) return 0;
        if(target>nums[len-1]) return len;
        int start = 0;
        int end = len-1;
        int middle =0;


        while(start<end){
            middle = start + (end - start) / 2;
            if(nums[middle]<target)
                start=middle+1;
            else
                end=middle;
        }

        return end;
        
    }
}

74. 搜索二维矩阵

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int right = matrix[0].length-1;
        int up = 0;

        while(up<matrix.length && right>=0){
            if(matrix[up][right]<target)
                up++;
            if(up>=matrix.length) break;

            if(matrix[up][right]>target)
                right--;
            if(right<0) break;

            if(matrix[up][right]==target) 
                return true;
        }

        return false;
    }
}

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

class Solution {
    public int[] searchRange(int[] nums, int target) {

        if(nums.length==0) return new int[]{-1, -1};

        int start = 0;
        int end = nums.length-1;
        while(start<end){
            int middle = start + ( end - start ) / 2;
            if(nums[middle]<target)
                start=middle+1;
            else
                end=middle;
        }

        if(nums[end]!=target) 
            return new int[]{-1, -1};


        while(start>=0 && nums[start]==target ) start--;
        while(end<nums.length && nums[end]==target) end++;

        return new int[]{start+1, end-1};
        
    }
}

33. 搜索旋转排序数组

class Solution {
    public int search(int[] nums, int target) {

        int index = 0;
        //找到反转处的下标
        for(int i=0; i<nums.length-1; i++){
            if(nums[i] > nums[i+1]){
                index = i;
                break;
            }
        }

        int frontSearch = searchInsert(nums, target, 0, index);
        int lastSearch = searchInsert(nums, target, index+1, nums.length-1);

        if(lastSearch==-1)
            if(frontSearch==-1)
                return -1;
            else
                return frontSearch;
        else
            return lastSearch;
    }

    
    public int searchInsert(int[] nums, int target, int start, int end) {
        
        int len = nums.length;
        while(start<end){
            int middle = start + (end - start) / 2;
            if(nums[middle]<target)
                start=middle+1;
            else
                end=middle;
        }

        if(nums[end]!=target)
            return -1;
        else
            return end;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;

        if(len==0) return -1;
        if(len==1 && nums[0]==target) return 0;
        if(len==1 && nums[0]!=target) return -1;

        int start=0;
        int end=len-1;

        //注意<=
        while(start<=end){
            int middle = start + (end - start) / 2;

            if(nums[middle]==target)
                return middle;

            if(nums[start]<=nums[middle]){
                //左一半是有序的
                if(nums[start]<=target && target<nums[middle])
                    end = middle-1;
                else
                    start = middle+1;

            }else{
                //右一半是有序的
                if(nums[middle]<target && target<=nums[end])
                    start = middle+1;
                else
                    end = middle-1;
            }
        }

        return -1;
            
    }
    
}

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

超明显写法Sleepy Ellis4vY

class Solution {
    public int findMin(int[] nums) {
        int len = nums.length;

        if(len==1 || nums[0]<nums[len-1]) 
            return nums[0];

        int left = 0;
        int right = len-1;

        //左闭右闭
        while(left<=right){
            int middle = left - (left - right) / 2;
            if(middle!=0 && nums[middle]<nums[middle-1])
                return nums[middle];
            if(nums[middle]>nums[right])
                left = middle+1;
            else
                right = middle-1;
        }
        return left;
    }
}