力扣35，74
力扣35.搜索插入位置
原题，题目描述：
简单题，考察最基本的二分查找，不必多说，直接上代码：
代码一
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length-1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else{
right = mid - 1;
}
}
return left;
}
}
力扣74.搜索二维矩阵
原题，题目描述：
这题比起上一题其实也没提高多少难度，只是增加了一个二分查找的维度，我们需要两次二分查找。首先矩阵的行列都是有序递增的，并且后一行的第一个元素一定大于上一行最后一个元素。那我们可以直接对最后一列做二分查找，找到第一个大于目标元素的行。这里直接使用上一题的代码即可。找到行后我们直接对这一行再做二分查找，即可搜索是否包含元素，下面看代码：
代码二
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (matrix[mid][n - 1] == target) {
return true;
} else if (matrix[mid][n - 1] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if(left>=m){
return false;
}
if (matrix[left][0] > target) {
return false;
}
if(matrix[left][0] == target){
return true;
}
int row = left;
left = 0;
right = n - 1;
while (left <= right) {
mid = (left + right) / 2;
if (matrix[row][mid] == target) {
return true;
} else if (matrix[row][mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
代码基本按照思路一比一写的，理解起来应该没有难度。不过这题很有意思的是，直接暴力遍历也是0毫秒，打败百分百。