定義

平常我們認(rèn)為的查找，在計算機(jī)算法中，稍稍有一些不同

在計算機(jī)科學(xué)中定義為：在一些（有序的/無序的）數(shù)據(jù)元素中，通過一定的方法找出與給定關(guān)鍵字相同的數(shù)據(jù)元素的過程叫做查找。也就是根據(jù)給定的某個值，在查找表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。——百科

1. 查找解決的問題的輸入是：
   • 輸入1：一堆有序或無序的數(shù)據(jù)元素。也就是查找的邏輯結(jié)構(gòu)是基于集合的。
     但是因為集合中元素和元素之間本質(zhì)上沒有關(guān)系，所以需要實現(xiàn)查找，就要把這種邏輯結(jié)構(gòu)向我們平常處理的線性表、樹等邏輯結(jié)構(gòu)進(jìn)行轉(zhuǎn)換。
     （值得注意的是，查找的數(shù)據(jù)元素雖然說是基于集合的，但是可以是相同的，但是如果當(dāng)數(shù)據(jù)元素是主關(guān)鍵字的時候，是有互異性的。）
   • 輸入2：關(guān)鍵字。搜索過程中我們要輸入的是key，而不是其它。key有主關(guān)鍵字和次關(guān)鍵字兩種，主關(guān)鍵字是唯一標(biāo)識數(shù)據(jù)記錄的，而次關(guān)鍵字不是唯一的。

關(guān)鍵字、數(shù)據(jù)記錄、數(shù)據(jù)項
如何區(qū)分這三個的關(guān)系呢，一個關(guān)鍵字就是一個數(shù)據(jù)項。當(dāng)一個關(guān)鍵字（一個數(shù)據(jù)項）有互異性的時候它就可以代表一整條數(shù)據(jù)記錄（數(shù)據(jù)記錄是多個數(shù)據(jù)項的組合）。

2. 查找解決的問題的輸出是：

   • 一整條數(shù)據(jù)記錄

3. 查找的兩種分類

   • 靜態(tài)查找：就是單純的查找，不改變數(shù)據(jù)
   • 動態(tài)查找：不僅僅是查找，查找到了還要對數(shù)據(jù)進(jìn)行操作（增刪）

順序表查找

接下來我們就通過把查找的集合型邏輯結(jié)構(gòu)轉(zhuǎn)換為線性表的結(jié)構(gòu)，再對線性表進(jìn)行查找，一般利用線性表結(jié)構(gòu)通常是靜態(tài)查找

順序查找

如果線性表沒有順序——

public static int sequenceSearch(int[] list, int key) {
        for (int i = 0; i < list.length; i++) {
            // 找到該元素，返回位置序號
            if (list[i] == key) {
                return i;
            }
        }
        // 沒有找到
        return -1;
}

可以對順序查找進(jìn)行優(yōu)化，不需要每次都判斷i是否越界：設(shè)置哨兵，遇到哨兵則證明查找結(jié)束跳出循環(huán)，具體代碼此處略

有序查找（有序表查找）

不同于順序表查找，在這里我們把元素們按某種順序進(jìn)行排列好，可以進(jìn)行折半查找，更快。

二分查找

對于算法，我一般都是把步驟和具體代碼實現(xiàn)進(jìn)行對應(yīng)，再去分析每一步實現(xiàn)的代碼有什么特點
算法步驟

1. 找到中間元素，比較異同
2. 若不同，選擇其中一個半數(shù)組當(dāng)成一個新數(shù)組
3. 若相同，返回中間元素，跳出循環(huán)
4. 重復(fù)第1、2、3步，直到數(shù)組只剩一個元素

圖1

要點
1 對于算法步驟3，重復(fù)哪幾步就在哪幾步前面加循環(huán)，如果重復(fù)第一步，就意味著循環(huán)從第一步前就開始
2 一個數(shù)組的變化只要用“指針”標(biāo)明數(shù)組的實際物理位置下標(biāo)從哪里開始到哪里結(jié)束
3 找中間元素就是把頭尾相加的一半（(low+high)/2）
4 如何判斷數(shù)組只有一個元素了——low==high

插值查找

和二分查找差別就在于，每次都會篩選按照百分比去選擇數(shù)組的分割點。

二分查找是不會錯過關(guān)鍵字的算法，但是對于分布均勻的數(shù)組，效率相較低；插值查找對于分布均勻的數(shù)組，查找效率相對較高，但是對于極端的分布的數(shù)組是效率很低的

它們的時間復(fù)雜度都是O(logn)

斐波那契查找算法

它的篩選方法也是通過分割，但是是按照黃金分割去選擇分割點，除此之外思路上并沒有與前面兩者很大區(qū)別，算法復(fù)雜度依然是O(logn)，但其優(yōu)點是：整個算法只需要進(jìn)行加減運算

在算法步驟上&代碼上的區(qū)別：

1. 需要增加斐波那契數(shù)列數(shù)組
2. 對原數(shù)組需要進(jìn)行補(bǔ)充至符合斐波那契數(shù)列的長度
3. 分割點不同意味著mid的計算公式需要變化
4. 分割數(shù)組的時候需要根據(jù)左右來更新下一個分割點的位置在哪（k-1或者是k-2）

線性索引查找

圖2

如圖2，關(guān)鍵碼里面的關(guān)鍵字都是一樣的，只是我把關(guān)鍵碼單獨一項拿出來單獨成表，便于維護(hù)。

稠密索引

如圖2，把所有的數(shù)據(jù)記錄的主關(guān)鍵字都拿出來建成索引表

分塊索引

也是把主關(guān)鍵字拿出來建索引表，但是就是把主關(guān)鍵字分成一個個的大類，比如1-10，10-20等范圍

圖3

它的時間復(fù)雜度分兩步，第一步是分塊查找，第二步是塊內(nèi)查找（塊內(nèi)一般是無序的，但是可以是有序的），所以如果兩步都是采用順序查找，就發(fā)現(xiàn)查找平均長度是根號n加1。比O(n)會快。

算法平均長度：就是一個算法走的步數(shù)，然后平均下來的值。大O記法就是平均長度里面的最高項。

倒排索引

倒排索引就是用次關(guān)鍵字建成一張表。次關(guān)鍵字其實就是數(shù)據(jù)記錄里面一些屬性值
倒排索引指的是通過屬性值來確定數(shù)據(jù)記錄，而正排索引就是說通過數(shù)據(jù)記錄再找到里面的屬性值。

通俗來講，當(dāng)搜索一個字符串“you”的時候（“you”就是屬性值）：

1.正排索引的查找算法：
文檔1有沒有“you”-->文檔2有沒有“you”-->文檔3有沒有“you”
（每一個數(shù)據(jù)記錄有沒有此屬性值）

2.倒排索引的查找算法：
找到“you”-->“you”存在與文檔1、2、3
如圖3

圖3