Leetcode 74. 搜索二维矩阵 (Day 22) JavaScript

两次二分

varsearchMatrix=function(matrix,target){constm=matrix.length;constn=matrix[0].length;letleft=0,right=m-1;letres=-1;while(left<=right){letmid=Math.floor((left+right)/2);if(matrix[mid][n-1]==target){res=mid;break;}elseif(matrix[mid][n-1]<target)left=mid+1;elseright=mid-1;}if(left==m)returnfalse;if(res>=0)returntrue;elseres=left;left=0,right=n-1;while(left<=right){letmid=Math.floor((left+right)/2);if(matrix[res][mid]==target){returntrue;}elseif(matrix[res][mid]<target)left=mid+1;elseright=mid-1;}returnfalse;};

优化版

varsearchMatrix=function(matrix,target){// 二分搜索constm=matrix.length;constn=matrix[0].length;letleft=0;letright=m*n-1;while(left<=right){constmid=Math.floor(left+(right-left)/2);// 把一维下标 mid 映射回二维坐标constx=matrix[Math.floor(mid/n)][mid%n];if(x===target)returntrue;if(x>target){right=mid-1;}else{left=mid+1;}}returnfalse;};