【題目描述】

創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站制作、做網(wǎng)站、方城網(wǎng)絡(luò)推廣、小程序開發(fā)、方城網(wǎng)絡(luò)營(yíng)銷、方城企業(yè)策劃、方城品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供方城建站搭建服務(wù)，24小時(shí)服務(wù)熱線：028-86922220，官方網(wǎng)址：www.cdcxhl.com

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.

寫出一個(gè)高效的算法來(lái)搜索 m × n矩陣中的值。

這個(gè)矩陣具有以下特性：每行中的整數(shù)從左到右是排序的。每行的第一個(gè)數(shù)大于上一行的最后一個(gè)整數(shù)。

【題目鏈接】

http://www.lintcode.com/en/problem/search-a-2d-matrix/

【題目解析】

對(duì)于這個(gè)給定的矩陣，我們?nèi)绻胋rute force解法，用兩個(gè)嵌套循環(huán)，O(n2)便可以得到答案.但是我們需要注意的是這道題已經(jīng)給定了這個(gè)矩陣的兩個(gè)特性，這兩個(gè)特性對(duì)于提

高我們算法的時(shí)間復(fù)雜度有很大幫助，首先我們給出一個(gè)O(n)的解法，也就是說(shuō)我們可以固定住右上角的元素，根據(jù)遞增或者遞減的規(guī)律，我們可以判斷這個(gè)給定的數(shù)值是否存在于這個(gè)矩陣當(dāng)中.

【參考答案】

http://www.jiuzhang.com/solutions/search-a-2d-matrix/