掌握二分查詢
二分查詢分析:二分查詢是在已排序完畢的基礎上進行的,用兩個下標變數記錄下標的移動情況,反映出查詢範圍的縮小 ,再用一個下標變數記錄陣列一動態元素值,將其與查詢值比對是否相等。
假設查詢元素33,下標變數S M E記錄下標,迴圈查詢條件為S<E ,若有array[M]==33,則查詢成功,返回array[M],結束查詢;否則當S大於E,返回一個統一值如-1,結束查詢。
陣列元素:11 22 33 44 55 66 77 88 99
陣列下標:0 1 2 3 4 5 6 7 8
方法過程:
S M E 記錄下標初始值,其中M=(S+E)/2
下標 0 8 55
第一次迴圈:S<E, array[M]>33,往左邊查詢,
下標 3 4
E=M-1
下標 1 0 3
M=(S+E)/2 結束第一次。
下標 0 3 22
第二次迴圈:S<E,array[M]<33,往右邊查詢,
下標 2 1
S=M+1
下標 2 2 3
M=(S+E)/2 結束第二次
下標 2 3 33
第三次迴圈:S<E,array[M]==33,返回 33,全過程結束
(若是查詢32,此時array[M]>32,往左邊查詢,
下標 1 2
E=M-1
下標 1 2 1
M=(S+E)/2
第四次迴圈:
下標 2 1
S>E,不滿足迴圈條件,退出,宣告查詢失敗,返回一個統一值 如 -1)
我的程式碼實現:
public class BinSearch {
public static int binSearch(int[] array,int val) {
int startIndex=0,endIndex=array.length-1;//定義變數存放首尾元素下標以及中間元素下標
int midIndex=(startIndex+endIndex)/2;
while(startIndex<=endIndex) {
if(array[midIndex]==val) {
return array[midIndex];
}else if(array[midIndex]>val) {
endIndex=midIndex-1;
midIndex=(startIndex+endIndex)/2;
}else if(array[midIndex]<val) {
startIndex=midIndex+1;
midIndex=(startIndex+endIndex)/2;
}
}
return -1;
}
public static void main(String[] args) {
int[] array= {11,22,33,44,55,66,77,88,99}; // TODO Auto-generated method stub
System.out.print("在下面陣列中查詢:\n");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
System.out.println("查詢99結果:");
if(binSearch(array,99)==99)
System.out.println("找到 99.");
else
System.out.println("沒有找到99.");
System.out.println("查詢23結果:");
if(binSearch(array,23)==-1)
System.out.println("未找到。");
}
}
執行結果:
在下面陣列中查詢:
11 22 33 44 55 66 77 88 99
查詢99結果:
找到 99.
查詢23結果:
未找到。