写点什么

LeetCode 题解:74. 搜索二维矩阵,二分查找,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 02 月 08 日
LeetCode题解:74. 搜索二维矩阵,二分查找,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/search-a-2d-matrix/


解题思路:


  1. 该题实际上是将一个单调递增的数组,转换为了一个矩阵,那么可以用二分查找来解决。

  2. 计算中点索引时,需要将其转换为矩阵中的坐标。


/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */var searchMatrix = function (matrix, target) {  const colLength = matrix[0].length; // 缓存一行的元素数量,用于计算真实索引  let left = 0; // 二分查找左边界  let right = matrix.length * colLength - 1; // 二分查找右边界
// 当左右边界相遇时,查找结束 while (left <= right) { // 计算当前查找区域的中点 const mid = (left + right) >> 1; // 计算当前中点在矩阵中的哪一行 const row = Math.floor(mid / colLength); // 计算当前中点在矩阵中的哪一列 const col = mid % colLength;
// 如果当前中点值等于目标,查找成功 if (matrix[row][col] === target) { return true; }
// 如果中值大于目标,表示目标在左半边,将右边界移动到左半边继续查找 if (matrix[row][col] > target) { right = mid - 1; } else { // 如果中值小于目标,表示目标在右半边,将左边界移动到右半边继续查找 left = mid + 1; } }
return false;};
复制代码


发布于: 2021 年 02 月 08 日阅读数: 13
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:74. 搜索二维矩阵,二分查找,JavaScript,详细注释