算法练习题18——leetcode240搜索二维矩阵||（二分）
题目描述编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序分列。
每列的元素从上到下升序分列。
https://i-blog.csdnimg.cn/direct/89ea4fe9a3f3448e8bdf76e89aa6f9b0.png
https://i-blog.csdnimg.cn/direct/be46c576b8f44c279e52fe127be39334.png
代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int[] row:matrix){
int index = search(row,target);
if(index>=0){
return true;
}
}
return false;
}
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1; // 初始化指针
while (low <= high) {
int mid = (high - low) / 2 + low; // 计算中点，防止整数溢出
int num = nums; // 获取中点值
if (num == target) { // 找到目标值
return mid;
} else if (num > target) { // 目标值在左半部分
high = mid - 1;
} else { // 目标值在右半部分
low = mid + 1;
}
}
return -1; // 没有找到目标值
}
} 复杂度分析
[*] 时间复杂度：O(mlogn)。对一行使用二分查找的时间复杂度为 O(logn)，最多需要进行 m 次二分查找。
[*] 空间复杂度：O(1)。
示例和表明
假设我们有一个升序的数组 nums = ，目标值 target = 7。让我们看看这个算法如何找到目标值：
[*] 初始状态：
[*]数组：
[*]low = 0，high = 5（数组的长度为 6，所以索引范围是 0 到 5）
[*] 第一次迭代：
[*]盘算中点索引：mid = (high - low) / 2 + low = (5 - 0) / 2 + 0 = 2
[*]中点值：nums = nums = 5
[*]比较：5 < 7（中点值小于目标值）
[*]更新指针：将 low 指针移动到 mid + 1 = 3，high 保持不变（5）
[*] 第二次迭代：
[*]新的范围：（索引 3 到 5）
[*]盘算中点索引：mid = (high - low) / 2 + low = (5 - 3) / 2 + 3 = 4
[*]中点值：nums = nums = 9
[*]比较：9 > 7（中点值大于目标值）
[*]更新指针：将 high 指针移动到 mid - 1 = 3，low 保持不变（3）
[*] 第三次迭代：
[*]新的范围：（索引 3 到 3）
[*]盘算中点索引：mid = (high - low) / 2 + low = (3 - 3) / 2 + 3 = 3
[*]中点值：nums = nums = 7
[*]比较：7 == 7（中点值便是目标值）
[*]找到目标值，返回 mid = 3
效果
目标值 7 在数组中的索引是 3，所以函数返回 3。
另一个示例
假设我们有同样的数组 nums = ，但目标值 target = 4，这个值不在数组中。我们看看算法如何工作：
[*] 初始状态：
[*]数组：
[*]low = 0，high = 5
[*] 第一次迭代：
[*]盘算中点索引：mid = (high - low) / 2 + low = (5 - 0) / 2 + 0 = 2
[*]中点值：nums = nums = 5
[*]比较：5 > 4（中点值大于目标值）
[*]更新指针：将 high 指针移动到 mid - 1 = 1，low 保持不变（0）
[*] 第二次迭代：
[*]新的范围：（索引 0 到 1）
[*]盘算中点索引：mid = (high - low) / 2 + low = (1 - 0) / 2 + 0 = 0
[*]中点值：nums = nums = 1
[*]比较：1 < 4（中点值小于目标值）
[*]更新指针：将 low 指针移动到 mid + 1 = 1，high 保持不变（1）
[*] 第三次迭代：
[*]新的范围：（索引 1 到 1）
[*]盘算中点索引：mid = (high - low) / 2 + low = (1 - 1) / 2 + 1 = 1
[*]中点值：nums = nums = 3
[*]比较：3 < 4（中点值小于目标值）
[*]更新指针：将 low 指针移动到 mid + 1 = 2
[*] 竣事条件：
[*]现在 low = 2，high = 1，满足 low > high，循环竣事。
[*]目标值 4 不在数组中，返回 -1。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]