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

多维坐标之间的映射转换

重塑矩阵

题目

java">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开始)，值为valuevoid 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];}
}

搜索二维矩阵

题目

java">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

题目

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

寻找峰值

搜索插入位置

题目

java">class Solution {//找到<targe的最大数的indexpublic 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;}
}

寻找峰值

题目

java">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左边，包括midright=mid;}}return left;}
}

山脉数组的峰值索引

题目

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

java">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的左边，包括midright=mid;}}return left;}
}

统计目标成绩的出现次数

题目

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

特殊数组的二分搜索

搜索旋转排序数组

题目

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