public int searchInsert(int[] nums, int target) {
// 思路：找到第一个 >= target 的元素位置
int left = 0;
int right = nums.length - 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if (nums[left] >= target) {
return left;
} else if (nums[left] < target && target <= nums[right]) {
return left + 1;
} else {
// 目标值比所有值都大
return right + 1;
}
}
搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
public boolean searchMatrix(int[][] matrix, int target) {
// 思路：将2维数组转为1维数组 进行二分搜索
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int left = 0;
int right = row * col - 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
// 获取2维数组对应值
int val = matrix[mid/col][mid%col];
if (val < target) {
left = mid;
} else if (val > target) {
right = mid;
} else {
return true;
}
}
if (matrix[left/col][left%col] == target || matrix[right/col][right%col] == target) {
return true;
}
return false;
}
public int findMin(int[] nums) {
// 思路：最后一个值作为target，然后往左移动，最后比较start、end的值
if (nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
// 最后一个元素值为target
if (nums[mid] > nums[right]) {
left = mid;
} else {
right = mid;
}
}
return Math.min(nums[left], nums[right]);
}
