| 查找算法（比較） | 基本思想 |
| 順序查找 | 順序查找也稱為線形查找，屬于無序查找算法。從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等于k的結點，表示查找失敗。 |
| ? | ? |
| ? | ? |
| ? | ? |
| ? | ? |
| ? | ? |
| ? | ? |
1. 順序查找
說明：順序查找適合于存儲結構為順序存儲或鏈接存儲的線性表。
基本思想：順序查找也稱為線形查找，屬于無序查找算法。從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等于k的結點，表示查找失敗。
復雜度分析：
查找成功時的平均查找長度為：（假設每個數據元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
當查找不成功時，需要n+1次比較，時間復雜度為O(n);
當查找不成功時，需要n+1次比較，時間復雜度為O(n);
所以，順序查找的時間復雜度為O(n)。
public class Test{public static void main(String[] args) {int[] a = new int[args.length];for(int i=0;i<args.length;i++){a[i]=Integer.parseInt(args[i]);//int type packaging type}print(a);System.out.println("result:"+sequenceSearch(a,3));}private static boolean sequenceSearch(int a[],int value){int i ;for(i = 0 ;i<a.length;i++){if(a[i] == value){return true;}}return false;}private static void print( int[] a){for(int i = 0 ;i<a.length ;i++){System.out.print(a[i]+" ");}System.out.println();}}運行結果：
<------------------------------------二分查找----------------------------------------------------->
二分查找
說明：元素必須是有序的，如果是無序的則要先進行排序操作。
基本思想：也稱為是折半查找，屬于有序查找算法。用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查找成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束發現表中沒有這樣的結點。
復雜度分析：最壞情況下，關鍵詞比較次數為log2(n+1)，且期望時間復雜度為O(log2n)；
注：折半查找的前提條件是需要有序表順序存儲，對于靜態查找表，一次排序后不再變化，折半查找能得到不錯的效率。但對于需要頻繁執行插入或刪除操作的數據集來說，維護有序的排序會帶來不小的工作量，那就不建議使用。——《大話數據結構》
《版本1》
private static boolean BinarySearch1(int a[], int value){int low, high, mid;low = 0;high = a.length;while(low<=high){mid = (low+high)/2;if(a[mid]==value)return true;if(a[mid]>value)high = mid-1;if(a[mid]<value)low = mid+1;}return false;
}《版本2：遞歸》
private static int BinarySearch2(int a[], int value, int low, int high){int mid = low+(high-low)/2;if(a[mid]==value){return mid;}if(a[mid]>value){return BinarySearch2(a, value, low, mid-1);}if(a[mid]<value){return BinarySearch2(a, value, mid+1, high);}return 0;}<------------------------------------------插值查找-------------------------------------------->
?插值查找
在介紹插值查找之前，首先考慮一個新問題，為什么上述算法一定要是折半，而不是折四分之一或者折更多呢？
打個比方，在英文字典里面查“apple”，你下意識翻開字典是翻前面的書頁還是后面的書頁呢？如果再讓你查“zoo”，你又怎么查？很顯然，這里你絕對不會是從中間開始查起，而是有一定目的的往前或往后翻。
同樣的，比如要在取值范圍1 ~ 10000 之間 100 個元素從小到大均勻分布的數組中查找5， 我們自然會考慮從數組下標較小的開始查找。
經過以上分析，折半查找這種查找方式，不是自適應的（也就是說是傻瓜式的）。二分查找中查找點計算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);
通過類比，我們可以將查找的點改進為如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
也就是將上述的比例參數1/2改進為自適應的，根據關鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關鍵字key，這樣也就間接地減少了比較次數。
基本思想：基于二分查找算法，將查找點的選擇改進為自適應選擇，可以提高查找效率。當然，差值查找也屬于有序查找。
注：對于表長較大，而關鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。
復雜度分析：查找成功或者失敗的時間復雜度均為O(log2(log2n))。
private static int InsertionSearch(int a[], int value, int low, int high){int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);if(a[mid]==value){return mid;}if(a[mid]>value){return InsertionSearch(a, value, low, mid-1);}if(a[mid]<value){return InsertionSearch(a, value, mid+1, high);}return 0;}
