如何進(jìn)入Google,面試算法之道：在雙升序二維數(shù)組中的快速查找

給定一個(gè)二維數(shù)組找颓，它的行和列都是已經(jīng)按升序排列粒竖，請?jiān)O(shè)計(jì)一個(gè)算法氧骤，對于給定某個(gè)值x呻疹，判斷該值是否包含在數(shù)組中。例如給定一個(gè)二維數(shù)組如下：
A = {
{2, 4, 6, 8 , 10},
{12, 14, 16, 18, 20},
{22, 24, 26, 28, 30},
{32, 34, 36, 38, 40},
{42, 44, 46, 48, 50},
}

如果給定的x值是34筹陵，那么算法返回該值所在的行和列刽锤，也就是3和2，如果x的值是35朦佩，那么算法返回該值不存在并思。

在我們以前的算法討論中曾經(jīng)提到過一個(gè)法則，當(dāng)看到有數(shù)組時(shí)语稠，首先想到的就是排序宋彼。如果看到排序弄砍，首先想到的是二分查找，對于給定數(shù)組输涕，它已經(jīng)排好序了音婶，那么我們可以考慮用二分查找來判斷給定元素是否在數(shù)組中。

我們先看最簡單的做法莱坎，最簡單的莫過于一個(gè)個(gè)查看衣式，也就是算法遍歷每一個(gè)元素，看看是否與給定數(shù)值相等檐什。這種做法算法復(fù)雜度是O(n*n)碴卧。

第二種做法就是使用二分查找，由于每一行都是升序排列的厢汹，那么我們可以對應(yīng)于一行螟深，先用二分查找法，探尋給定元素是否在某一行烫葬，如果不再這行界弧，那么我們選擇新一行，再次使用二分查找去檢測給定元素是否存在給定行搭综。第二種做法效率比第一種要高垢箕，因?yàn)槎植檎业膹?fù)雜度是lg(n)，因此算法的復(fù)雜度是O(n*lg(n))兑巾。

我們能否更進(jìn)一步条获，找到更好的算法呢？題目給定的特征是蒋歌，數(shù)組的行和列都是升序排序的帅掘，第二種做法只利用了行是升序排列這一性質(zhì)，對于列的升序排列并未利用到堂油，如果能夠利用到這一特性的話修档，那么我們就可以設(shè)計(jì)出更高效的算法，由此我們得到第三種算法如下,假設(shè)數(shù)組的長度為n：

1, 用x與A[0][n-1]比較府框，如果 x < A[0][n-1], 那根據(jù)數(shù)組每一列都是升序排序的特性吱窝，我們可以排除掉數(shù)組的最后一列。

2, 如果x > A[0][n-1], 那么根據(jù)數(shù)組每一行按照升序排列的特性迫靖，我們就可以排除掉數(shù)組的第0行院峡。

3, 如果x == A[0][n-1], 算法直接返回。

4, 如果算法查詢的行數(shù)超過n,或者列數(shù)小于0系宜，那表明數(shù)組不包含給定元素照激。

根據(jù)上述算法描述，我們給出算法的代碼實(shí)現(xiàn)如下：


public class TwoDArraySearch {
    private int[][] searchArray;
    private int seachValue;
    
    private int row = 0;
    private int col = 0;
    
    public int getRow () {
        return this.row;
    }
    
    public int getCol () {
        return this.col;
    }
    
    public TwoDArraySearch(int[][] array, int val) {
        this.searchArray = array;
        this.seachValue = val;
        this.col = array[0].length - 1;
    }
    
    boolean search() {
        while (this.row < this.searchArray[0].length && this.col >= 0) {
            if (this.searchArray[this.row][this.col] == this.seachValue) {
                return true;
            }
            
            if (this.seachValue > this.searchArray[this.row][this.col]) {
                this.row++;
            }else if (this.seachValue < this.searchArray[this.row][this.col]) {
                this.col--;
            }
        }
        
        return false;
    }
   
}

在程序的主入口中盹牧，我們設(shè)計(jì)數(shù)據(jù)如下：

import java.util.AbstractMap;
import java.util.AbstractMap.SimpleEntry;
import java.util.Arrays;
import java.util.Map.Entry;
import java.util.Random;

public class Search {
    
    public static void main(String[] args) {
       int[][] array = {
               {2, 4, 6, 8 , 10},
               {12, 14, 16, 18, 20},
               {22, 24, 26, 28, 30},
               {32, 34, 36, 38, 40},
               {42, 44, 46, 48, 50},
       };
       
       TwoDArraySearch s = new TwoDArraySearch(array, 34);
       if (s.search() == true) {
           System.out.println("Array contains element which is in row " + s.getRow() + " and in col " + s.getCol());
       } else {
           System.out.println("Array does not contain the given element");
       }
    }
}

代碼先構(gòu)造了一個(gè)行和列都按照升序排列的數(shù)組实抡，并設(shè)置要查詢的數(shù)值為34欠母，顯然該值包含在數(shù)組中，然后調(diào)用TwoDArraySearch 的search()函數(shù)吆寨，上面代碼運(yùn)行后結(jié)果如下：

這里寫圖片描述

根據(jù)輸出結(jié)果赏淌，我們可以判斷，算法的實(shí)現(xiàn)是正確的啄清。

我們再看看算法的復(fù)雜度六水，根據(jù)算法步驟描述，每當(dāng)執(zhí)行步驟1或2時(shí)辣卒，算法都會排除掉一行或者一列的元素掷贾，這意味著，算法要檢測的元素?cái)?shù)量減少了n個(gè)荣茫，一個(gè)n*n的數(shù)組想帅，它只有n行和n列，也就是說啡莉，步驟1和2最多只能執(zhí)行n次港准，因此第三種算法的復(fù)雜度是O(n)。

更詳細(xì)的講解和代碼調(diào)試演示過程咧欣，請點(diǎn)擊鏈接

更多技術(shù)信息浅缸，包括操作系統(tǒng)，編譯器魄咕，面試算法衩椒，機(jī)器學(xué)習(xí)，人工智能哮兰，請關(guān)照我的公眾號：

這里寫圖片描述