二分搜尋法
在使用二分搜尋法之前，要先確定陣列是否已經排序好了，假如我們有以下數列
2 5 6 8 7 9 4 1 3
第一步驟 : 先排序
可以使用上堂課教過的Selection Sort或是Bubble Sort，這裡就不再詳述
1 2 3 4 5 6 7 8 9
只有排序過的陣列，才可以使用二分搜尋法!!!
第二步驟：每次都從中間元素開始找
- 找到數值n
- 找到非我們要尋找的數值n
- 若找到的數值<數值n，只要找剩下左半邊就好 (數值n只可能出現在左半邊)
- 若找到的數值>數值n，只要找剩下右半邊就好 (數值n只可能出現在右半邊)
以尋找6為例，有底線的為尋找範圍
1 2 3 4 5 6 7 8 9 // 找到5(非6) => 6>5 => 6只有可能在右半邊
-----------------
1 2 3 4 5 6 7 8 9 // 找到7(非6) => 6<7 => 6只有可能在左半邊
-------
1 2 3 4 5 6 7 8 9 // 找到6!!
-
以尋找不存在的10為例
1 2 3 4 5 6 7 8 9 // 找到5(非10) => 10>5 => 10只有可能在右半邊
-----------------
1 2 3 4 5 6 7 8 9 // 找到7(非10) => 10>7 => 10只有可能在右半邊
-------
1 2 3 4 5 6 7 8 9 // 找到8(非10) => 10>8 => 10只有可能在右半邊
---
1 2 3 4 5 6 7 8 9 // 找到9(非10) => 10>9 => 10只有可能在右半邊
-
1 2 3 4 5 6 7 8 9 // 找不到
理解整個二元搜尋法的過程後，要開始思考如何用程式碼來實現
如何控制搜尋範圍呢？ 可以設兩個變數start跟end，取得範圍的明確開始結束位址，中間的數=(start+end)/2
什麼時候才會知道不可能找到此數值呢？以上段找10的情況為例
找到9後時 : start=8，end=8，但此時要找的10比9大，於是判斷在9的左邊，此時更改start=9，end不變=8
發現start竟然比end還要大了，照邏輯來說也不科學，此時就是找不到了
//PURPOSE:二分搜尋法
public class MainClass {
public static void main(String[] args){
//取得要搜尋的數
Scanner s=new Scanner(System.in);
int value[]={2,5,6,8,7,9,4,1,3};
System.out.print("請輸入您要尋找的數字:");
int target=s.nextInt();
boolean NotFound=true;
//排序陣列
BubbleSort(value);
//開始進行初始
int start=0;
int end=value.length-1;
int i=(start+end)/2;//中間數的位址
while(start<=end){//若起點大於終點，表示找不到數值，結束
System.out.println("找到"+value[i]);
if(value[i]==target){//若找得到數值
System.out.println("已找到，他是陣列裡編號第"+i+"的數");
NotFound=false;
break;
}else{//找不到數值就改變起終點
if(value[i]<target){
start=i+1;
}else{
end=i-1;
}
i=(start+end)/2;
}
}
if(NotFound){
System.out.println("找不到此數值");
}
}
public static void BubbleSort(int[] value){
for(int i=value.length-1;i>0;i--){
for(int j=0;j<i;j++){
//若前面的數比後面的大
if(value[j]>value[j+1]){
//交換此兩數
int z=value[j];
value[j]=value[j+1];
value[j+1]=z;
}
}
}
}
}
----------------------------------
請輸入您要尋找的數字:7
找到5
找到7
已找到，他是陣列裡編號第6的數
----------------------------------
請輸入您要尋找的數字:10
找到5
找到7
找到8
找到9
找不到此數值