什麼是查找？
查找是根據給定的某個值，在表中确定一個關鍵字的值等于給定值的記錄或資料元素。
查找算法的分類
若在查找的同時對表記錄做修改操作（如插入和删除），則相應的表稱之為動态查找表；
否則，稱之為靜态查找表。
此外，如果查找的全過程都在記憶體中進行，稱之為内查找；
反之，如果查找過程中需要通路外存，稱之為外查找。
查找算法性能比較的标準
——平均查找長度ASL（Average Search Length）
由于查找算法的主要運算是關鍵字的比較過程，是以通常把查找過程中對關鍵字需要執行的平均比較長度（也稱為平均比較次數）作為衡量一個查找算法效率優劣的比較标準。
選取查找算法的因素
(1) 使用什麼資料存儲結構（如線性表、樹形表等）。
(2) 表中的次序，即對無序表還是有序表進行查找。
要點
它是一種最簡單的查找算法，效率也很低下。
存儲結構
沒有存儲結構要求，可以無序，也可以有序。
基本思想
從資料結構線形表的一端開始，順序掃描，依次将掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；
若掃描結束仍沒有找到關鍵字等于k的結點，表示查找失敗。
核心代碼
<a></a>
public int orderSearch(int[] list, int length, int key) {
// 從前往後掃描list數組，如果有元素的值與key相等，直接傳回其位置
for (int i = 0; i < length; i++) {
if (key == list[i]) {
return i;
}
}
// 如果掃描完，說明沒有元素的值比對key，傳回-1，表示查找失敗
return -1;
}
算法分析
順序查找算法最好的情況是，第一個記錄即比對關鍵字，則需要比較 1 次；
最壞的情況是，最後一個記錄比對關鍵字，則需要比較 N 次。
是以，順序查找算法的平均查找長度為
ASL = (N + N-1 + ... + 2 + 1) / N = (N+1) / 2
順序查找的平均時間複雜度為O(N)。
二分查找又稱折半查找，它是一種效率較高的查找方法。
使用二分查找需要兩個前提：
(1) 必須是順序存儲結構。
(2) 必須是有序的表。
首先，将表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；
否則利用中間位置記錄将表分成前、後兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。
重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
public int binarySearch(int[] list, int length, int key) {
int low = 0, mid = 0, high = length - 1;
while (low <= high) {
mid = (low + high) / 2;
if (list[mid] == key) {
return mid; // 查找成功，直接傳回位置
} else if (list[mid] < key) {
low = mid + 1; // 關鍵字大于中間位置的值，則在大值區間[mid+1, high]繼續查找
} else {
high = mid - 1; // 關鍵字小于中間位置的值，則在小值區間[low, mid-1]繼續查找
二分查找的過程可看成一個二叉樹。
把查找區間的中間位置視為樹的根，左區間和右區間視為根的左子樹和右子樹。
由此得到的二叉樹，稱為二分查找的判定樹或比較樹。
由此可知，二分查找的平均查找長度實際上就是樹的高度O(log2N)。
分塊查找(Blocking Search)又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找方法。
分塊查找由于隻要求索引表是有序的，對塊内節點沒有排序要求，是以特别适合于節點動态變化的情況。
分塊查找表是由“分塊有序”的線性表和索引表兩部分構成的。
所謂“分塊有序”的線性表，是指：
假設要排序的表為R[0...N-1]，将表均勻分成b塊，前b-1塊中記錄個數為s=N/b，最後一塊記錄數小于等于s；
每一塊中的關鍵字不一定有序，但前一塊中的最大關鍵字必須小于後一塊中的最小關鍵字。
注：這是使用分塊查找的前提條件。
如上将表均勻分成b塊後，抽取各塊中的最大關鍵字和起始位置構成一個索引表IDX[0...b-1]。
由于表R是分塊有序的，是以索引表是一個遞增有序表。
下圖就是一個分塊查找表的存儲結構示意圖
分塊查找算法有兩個處理步驟：
(1) 首先查找索引表
因為分塊查找表是“分塊有序”的，是以我們可以通過索引表來鎖定關鍵字所在的區間。
又因為索引表是遞增有序的，是以查找索引可以使用順序查找或二分查找。
(2) 然後在已确定的塊中進行順序查找
因為塊中不一定是有序的，是以隻能使用順序查找。
代碼範例
分塊查找之JAVA實作
運作結果
線性表: 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85
構造索引表如下：
key = 14, link = 0
key = 34, link = 5
key = 66, link = 10
key = 85, link = 15
查找key = 85成功，位置為19
因為分塊查找實際上是兩次查找過程之和。若以二分查找來确定塊，顯然它的查找效率介于順序查找和二分查找之間。
(1) 以平均查找長度而言，二分查找 > 分塊查找 > 順序查找。
(2) 從适用性而言，順序查找無限制條件，二分查找僅适用于有序表，分塊查找要求“分塊有序”。
(3) 從存儲結構而言，順序查找和分塊查找既可用于順序表也可用于連結清單；而二分查找隻适用于順序表。
(4) 分塊查找綜合了順序查找和二分查找的優點，既可以較為快速，也能使用動态變化的要求。
本文轉自靜默虛空部落格園部落格，原文連結：http://www.cnblogs.com/jingmoxukong/p/4324179.html，如需轉載請自行聯系原作者
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)