leetcode Binary Search

leetcode 74题

Posted by franki on August 21, 2021

leetcode 74题 搜索二维矩阵

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

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

示例 1：

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

示例 2：

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

思路

利用二分搜索，其中low为0，high为矩阵行列数组的长度，中点为列的个数

代码

var searchMatrix = function(matrix, target) {
    // 利用二分法
    if (matrix.length === 0) {
        return false;
    }
    var low = 0, high = (matrix.length * matrix[0].length) - 1, mid = Math.floor(matrix[0].length);
    while (low <= high) {
        const middle = low + Math.floor((high - low) / 2);
        const divisor = Math.floor(middle / mid);  
        const remainer = Math.floor(middle % mid);
        if (matrix[divisor][remainer] === target) {
            return true;
        } else if (matrix[divisor][remainer] > target) {
            high = middle-1;
        } else {
            low = middle + 1;
        }
    }
    return false;
};

复杂度分析

  • 时间复杂度：O(logN)
  • 空间复杂度：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
    FRIENDS