折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果xa[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易于理解，但是要寫一個正確的二分搜索算法也不是一件簡單的事。第一個二分搜索算法早在1946年就出現了，但是第一個完全正確的二分搜索算法直到1962年才出現。Bentley在他的著作《Writing Correct PRograms》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索算法。問題的關鍵在于準確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理后可以發現它的具體算法是很直觀的，我們可用C++描述如下：
templateint BinarySearch(Type a[],const Type& x,int n){int left=0;int right=n-1;while(left<=right){int middle=(left+right)/2;if (x==a[middle]) return middle;if (x>a[middle]) left=middle+1;else right=middle-1;}return -1;}模板函數BinarySearch在a[0]<=a[1]<=…<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目了然。
java中的實例如下：
public class TestSearch {public static void main(String[] args) {int a[] = { 1, 3, 6, 8, 9, 10, 12, 18, 20, 34 };int i = 12;//System.out.println(search(a, i));System.out.println(binarySearch(a, i));}public static int search(int[] a, int num) {for(int i=0; i<a.length; i++) {if(a == num) return i;}return -1;}public static int binarySearch(int[]a, int num) {if (a.length==0) return -1;int startPos = 0;int endPos = a.length-1;int m = (startPos + endPos) / 2;while(startPos <= endPos){if(num == a) return m;if(num > a) {startPos = m + 1;}if(num < a) {endPos = m -1;}m = (startPos + endPos) / 2;}return -1;}}新聞熱點
疑難解答
