【二分搜索题目】

这里写目录标题 多维坐标之间的映射转换重塑矩阵搜索二维矩阵搜索二维矩阵2 寻找峰值搜索插入位置寻找峰值山脉数组的峰值索引统计目标成绩的出现次数 特殊数组的二分搜索搜索旋转排序数组

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

多维坐标之间的映射转换 重塑矩阵

题目

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; } }