leetcode Binary Search

leetcode 74题

Posted by franki on November 23, 2020

leetcode 74题 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
输出：true

示例 2

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
输出：false

示例 3

输入：matrix = [], target = 0
输出：false

思路

利用二分法，把矩阵想像成一个数组，从数组里面去寻找target

代码

var searchMatrix = function(matrix, target) {
    let m = matrix.length;
    if (m == 0) return false;
    let n = matrix[0].length;

    // 二分查找
    let left = 0, right = m * n - 1;
    let pivotIdx, pivotElement;
    while (left <= right) {
      pivotIdx = (left + right) >> 1;
      pivotElement = matrix[Math.floor(pivotIdx / n)][pivotIdx % n];
      if (target == pivotElement) return true;
      else {
        if (target < pivotElement) right = pivotIdx - 1;
        else left = pivotIdx + 1;
      }
    }
    return false;
};

复杂度分析

  • 时间复杂度: O(logmn)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS