[LeetCode] 74. Search a 2D Matrix

【原题】

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]

Given target = 3, return true. 【解释】 给定一个二维数组每一行有序,行与行之间有序,给定一个target,要求返回该元素是否在二维数组中。 【思路】 有序自然想到二分查找。但这题需要使用两次二分查找,首先二分查找到行,然后在该行中再使用二分(刚开始,使用顺序查找得到行号也可以过)。假设二维矩阵为mxn,则算法的复杂度为O(logm+logn)O(logm+logn).

public class Solution {
//查找列
        public boolean binarySearchCol(int[][] matrix, int row, int target){
        int left=0,right=matrix[row].length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(matrix[row][mid]==target)
                return true;
            if(matrix[row][mid]>target)
                right=mid-1;
            else 
                left=mid+1;
        }
        return matrix[row][left]==target;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length;
        if(m==0) return false;
        int n=matrix[0].length;
        if(n==0) return false;
        int left=0,right=m-1;
        /*注意这个二分查找要找到可能在的行,所以没有找到对应的target不能直接返回false,
        而要在最可能的一行单重继续查找*/
        while(left<right){
            int mid=(left+right+1)/2;
            if(matrix[mid][0]>target)
                right=mid-1;
            else if(matrix[mid][0]<target)
                left=mid;
            else return true;        
        }
       return  binarySearchCol(matrix, left,target);   
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ2134: 单选错位(期望乱搞)

Description ? Input n很大,为了避免读入耗时太多, 输入文件只有5个整数参数n, A, B, C, a1, 由上交的程序产生数列a。 下面给...

2585
来自专栏分布式系统进阶

Kafka源码分析-配置文件

作为Class KafkaConfig的伴生类,定义了创建KafkaConfig对象的工厂方法:

661
来自专栏大内老A

WCF技术剖析之一:通过一个ASP.NET程序模拟WCF基础架构

细算起来,已经有好几个月没有真正的写过文章了。近半年以来,一直忙于我的第一本WCF专著《WCF技术剖析》的写作,一直无暇管理自己的Blog。到目前为止《WCF技...

2397
来自专栏移动开发的那些事儿

Android Sqlite并发问题

如上异常堆栈中的错误信息error code 5: database is locked,经过查找发现code为5代表sqlite中的SQLITE_BUSY异常...

774
来自专栏开发技术

spring-boot-2.0.3不一样系列之源码篇 - run方法(三)之createApplicationContext,绝对有值得你看的地方

  此系列是针对springboot的启动,旨在于和大家一起来看看springboot启动的过程中到底做了一些什么事。如果大家对springboot的源码有所研...

1753
来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

33110
来自专栏向治洪

XMPP客户端库Smack 4.0.6版开发之二

XMPP客户端库Smack 4.0.6版开发之二 三、Smack库的特征 1、极度简单易用,API功能强大 发送一条文本消息给某个用户只需几行代码: Abst...

1925
来自专栏蘑菇先生的技术笔记

探索c#之不可变数据类型

1894
来自专栏salesforce零基础学习

salesforce零基础学习(八十七)Apex 中Picklist类型通过Control 字段值获取Dependent List 值

注:本篇解决方案内容实现转自:http://mysalesforceescapade.blogspot.com/2015/03/getting-dependen...

2756
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

721

扫码关注云+社区