【二分搜索题目】

二分搜索的精髓在于快速收缩搜索区间。

多维坐标之间的映射转换

重塑矩阵

题目

class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
       int m = mat.length, n = mat[0].length;
        // 如果想成功 reshape，元素个数应该相同
        if (r * c != m * n) {
            return mat;
        }

        int[][] res = new int[r][c];
        for (int i = 0; i < m * n; i++) {
            set(res, i, get(mat, i));
        }
        return res;
    }
    //再res的第index个(从0开始)，值为value
    void set(int[][]res,int index,int value){
        int col=res[0].length;
        int i=index/col;
        int j=index%col;
        res[i][j]=value;
    }
    int get(int[][]mat,int index){
        int col=mat[0].length;
        int i=index/col;
        int j=index%col;
        return mat[i][j];
    }
}

搜索二维矩阵

题目

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n=matrix.length;
        int m=matrix[0].length;
        int left=0,right=n*m-1,mid=0;
        while(left<=right){
            mid=(left+right)/2;
            int value=getMidValue(matrix,mid);
            if(value<target){
                left=mid+1;
            }else if(value>target){
                right=mid-1;
            }else{
                //找到了
                return true;
            }
        }
        return false;
    }
    int getMidValue(int[][]matrix,int index){
        int col=matrix[0].length;
        int i=index/col;
        int j=index%col;
        return matrix[i][j];
    }
}

搜索二维矩阵2

题目

class Solution {
    //从右上角开始，像左移动变小，向下移动变大
    public boolean searchMatrix(int[][] matrix, int target) {
        int n=matrix.length;
        int m=matrix[0].length;
        int i=0,j=m-1;
        while(i<n && j>=0){
            if(matrix[i][j]<target){
                //往下
                i++;
            }else if(matrix[i][j]>target){
                //往左
                j--;
            }else{
                //找到了
                return true;
            }
        }
        return false;
    }
}

寻找峰值

搜索插入位置

题目

class Solution {
    //找到<targe的最大数的index
    public int searchInsert(int[] nums, int target) {
        if(target<=nums[0]){
            return 0;
        }
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=(left+right+1)/2;//求最大，取右边
            if(nums[mid]<target){
                left=mid;
            }else{
                right=mid-1;
            }
        }
      
        return left+1;
    }
}

寻找峰值

题目

class Solution {
    //注意：寻找一个峰值, nums[-1] = nums[n] = -∞
    public int findPeakElement(int[] nums) {
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(nums[mid]<nums[mid+1]){
                //峰值在mid的右边
                left=mid+1;
            }else if(nums[mid]>nums[mid+1]){
                //峰值在mid左边，包括mid
                right=mid;
            }
        }
        return left;
    }
}

山脉数组的峰值索引

题目

跟上面一体类似，考虑mid的周边情况

class Solution {
    //考虑mid的周边情况
    public int peakIndexInMountainArray(int[] arr) {
        int left=0,right=arr.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(arr[mid]<arr[mid+1]){
                //峰值在mid右边
                left=mid+1;
            }else{
                //峰值在mid的左边，包括mid
                right=mid;
            }
        }
        return left;
    }
}

统计目标成绩的出现次数

题目

class Solution {
    //思路：寻找小于target的最大值 的index,然后往后遍历数数
    public int countTarget(int[] scores, int target) {
        
        int left=0,right=scores.length-1;
        if(left>right){
            //为空
            return 0;
        }

        while(left<right){
            int mid=(left+right+1)/2;
            if(scores[mid]<target){
                left=mid;
            }else{
                right=mid-1;
            }
        }

        int start=left;
        int count=0;
        for(int i=start;i<scores.length;i++){
            if(scores[i]==target){
                count++;
            }
            
        }
        return count;
    }
}

特殊数组的二分搜索

搜索旋转排序数组

题目

class Solution {
 
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        int leftVaule=nums[left],rightValue=nums[right];
        while(left<=right){
            int mid=(left+right)/2;

            if(nums[mid]==target){
                return mid;
            }
            
            if(nums[mid]>=nums[left]){
                //mid在左边悬崖or没有悬崖了
                if(target<nums[mid] && target>=nums[left]){
                    //target在有序区间[0,mid-1]
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{
                //mid在右边悬崖
                if(target<nums[mid]){
                    right=mid-1;
                }else{
                    if(target<nums[left]){
                        left=mid+1;
                    }else{
                        right=mid-1;
                    }
                }
            }
        }
        return -1;
    }
}