今天來整理一下查找。

什么是查找？

其實我真的不想解釋，嘻嘻，好吧。

來個官方一點的解釋吧：

查找(searching)是這樣一個過程，即在某個項目組中尋找某一指定目標(biāo)元素，或者確定該組中并不存在該目標(biāo)元素。 -from 《Java軟件結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)》

其實通俗點說就是看有沒有。真的好通俗！

有哪些查找方式？

一般常見的就兩個：

• 線性查找
• 二分查找

來，我們一個一個來看。這里，為了簡化問題，我們以整型數(shù)組作為我們要查找的序列。

好，開始！

線性查找 (linear search)

從名字中的“線性”我們大概能猜出來這種查找方式是怎么回事，線性嘛！一個一個找嘛！來直接看圖：

下面我用代碼來演示這一過程：

public class LinearSearchDemo {
    public static void main(String[] args) {
        int[] data = {2, 1, 4, 6, 12, 7};
        int target = 12;
        int searchIndex = search(data, target);
        if (searchIndex != -1) {
            System.out.println("found at: " + searchIndex);
        }else {
            System.out.println("not found");
        }
    }
    /*
    *@param  data   待查找的數(shù)組
    *@param  target 待查找的值
    *@return int    目標(biāo)值在數(shù)組中的索引，如果沒找到返回-1 
    */
    public static int search(int[] data, int target) {

        int length = data.length;
        
        //從頭遍歷數(shù)組中的各個值，如果找到目標(biāo)值就返回其索引
        for (int i = 0; i < length; i++) {
            if (data[i] == target) {
                return i;
            }
        }

        //代碼能走到這一步就說明上面的循環(huán)遍歷結(jié)束了也沒找到目標(biāo)值
        //即目標(biāo)值不存在于數(shù)組中
        return -1;

    }
}

輸出結(jié)果：
found at: 4

線性查找的效率當(dāng)然不是很高效，最壞情況是數(shù)組中沒有我們要找的目標(biāo)值，但是我們還是要遍歷完整個數(shù)組才能知道。但是它的優(yōu)點就是很簡單，特別的簡單，而且它還不要求待查找的數(shù)組是有序的。下面將要介紹的二分查找效率上要比線性查找高，但是它要求待查找的數(shù)組中的數(shù)據(jù)必須是有序的，我們接著來看。

二分查找( binary search)

先來個比較官方的解釋：

二分搜索（英語：binary search），也稱折半搜索（英語：half-interval search）、對數(shù)搜索（英語：logarithmic search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。 搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的 那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。 - from 維基百科

以上介紹參考自維基百科（PS：非常建議大家多上Google，多上Wikipedia，相信我，你會愛上它們的，哈哈~）

好，看完比較正式的解釋如果不太理解，沒關(guān)系，拿圖來說話：

二分法首先考察中間元素a[mid]，如果該值是我們要找的值，那好極了，直接找到了；如果不是的話，由于我們已經(jīng)知道數(shù)組是排好序的（二分法要求待查找的數(shù)組是有序的，本例假設(shè)是升序的，降序其實是一樣的），那就看目標(biāo)值target和a[mid]的關(guān)系是怎樣的：如果a[mid] > target則說明目標(biāo)值target如果存在的話一定在a[mid]的左側(cè)，因為左側(cè)都比a[mid]?。蝗绻鸻[mid] < target則說明目標(biāo)值如果存在的話一定在a[mid]的右側(cè)，因為右側(cè)都比a[mid]大。

因為a[mid]處在數(shù)組的中間位置，所以它的左側(cè)或者右側(cè)都是數(shù)組的一半，這樣每一次我們通過a[mid]和target的比較就可以排除掉一半的數(shù)據(jù)。最后只有兩種情況，要么我們找到了目標(biāo)值，要么我們排除了所有數(shù)據(jù)沒有找到目標(biāo)值。

由此看來，在處理已排序數(shù)據(jù)的查找工作時，二分查找法顯然效率高于線性查找法。這種優(yōu)勢在數(shù)據(jù)量越大的時候越明顯。

比如說，現(xiàn)在有序數(shù)組中含有100萬個數(shù)據(jù)，我們要求查找特定元素。如果使用線性查找法，我們必須對這一100萬個數(shù)據(jù)依次考察以確定出目標(biāo)元素是不是存在，最好的情況是目標(biāo)元素在數(shù)組的第一個位置a[0]，這樣只要一次就查找到目標(biāo)元素了，最壞情況是目標(biāo)元素在數(shù)組的最后a[999999]，這樣我們就得比較100萬次才能知道目標(biāo)元素到底在不在，平均下來看的話也需要50萬次比較。而如果使用二分查找法，我們大約做20次比較就可以知道目標(biāo)元素是不是存在于數(shù)組中了。

50萬 VS 20！

是不是很驚悚？為了達(dá)到目的我們可以使用不同的算法，但是這些算法之間的差異真的很大！ 在數(shù)據(jù)量越大的時候二分法的優(yōu)勢越明顯。

以下是我用Java代碼實現(xiàn)的，有遞歸的和非遞歸兩種方式。代碼注釋都寫的很清楚，相信大家對照著上面我的介紹應(yīng)該可以看得懂哈~

//二分查找：在有序數(shù)組中查找某一特定元素的搜索算法
public class BinarySearch {
    public static void main(String[] args) {
        int[] data = {1, 5, 6, 12, 15, 19, 23, 26, 30, 33, 37, 42, 53, 60};
        int target = 19;
        int index = binarySearch2(data, 0, data.length - 1, target);
        if (index > -1) {
            System.out.println("found ：" + index);
        }else {
            System.out.println("not found");
        }
    }

    /** 
     * 遞歸方法實現(xiàn)二分查找
     * @param data   已排序數(shù)組(這里假設(shè)是從小到大排序) 
     * @param from   起始位置 
     * @param to     終止位置 
     * @param target 要查找的值
     * @return 要查找的值在數(shù)組中的位置，如果沒找到則返回-1
     */  
    private static int binarySearch1(int[] data, int from, int to, int target) {
        if (from <= to) {
            int mid = from + (to - from) / 2;//中間位置，為了防止溢出使用這種方式求中間位置
            if (data[mid] < target) {//中間的值比目標(biāo)值小，則在左半邊繼續(xù)查找
                return binarySearch1(data, mid + 1, to, target);
            }else if(data[mid] > target){//中間的值比目標(biāo)值大，則在右半邊繼續(xù)查找
                return binarySearch1(data, from, mid - 1, target);    
            }else {//找到了，把找到的情況放在最后是因為多數(shù)情況下中間值不是大于就是小于，這樣做可以節(jié)省操作
                return mid;
            }
        }
        return -1;
    }

    /** 
     * 非遞歸方法實現(xiàn)二分查找
     * @param data   已排序數(shù)組(這里假設(shè)是從小到大排序) 
     * @param from   起始位置 
     * @param to     終止位置 
     * @param target 要查找的值
     * @return 要查找的值在數(shù)組中的位置，如果沒找到則返回-1
     */  
    private static int binarySearch2(int[] data, int from, int to, int target) {
        while(from <= to) {
            int mid = from + (to - from) / 2;
            if (data[mid] < target) {
                from = mid + 1;                
            }else if(data[mid] > target) {
                to = mid - 1;
            }else {//找到了，把找到的情況放在最后是因為多數(shù)情況下中間值不是大于就是小于，這樣做可以節(jié)省操作
                return mid;
            }
        }
        return -1;
    }
}
 
打印結(jié)果：
found: 5

到這里，文章差不多要結(jié)束了，最后我們再想一個問題，就是既然二分查找法效率這么高，甩線性查找法好多條街，那為什么還要線性查找法呢？

其實，線性查找法也不是一無是處，它最大的優(yōu)點就是簡單，特別簡單，傻瓜式的。你不是讓我找東西嗎，好啊，那我就把我兜里所有的東西一個一個拿出來看看有沒有，是不是很傻瓜式哈~

還有一點就是二分法本身也有局限性，那就是二分法必須要求待查數(shù)組是已排序的，比如我給你一個很大的數(shù)組，但是這個數(shù)組并沒有排序，那你如果想用二分查找法的話還必須先給數(shù)組排序，然后再查找。這樣就會造成除查找之外的額外成本（排序），至于這個額外成本是不是可承受的，就要看設(shè)計者自己權(quán)衡了，搞不好還不如人家線性查找快呢，嘿嘿~

好了，謝謝觀看~