(0-1)二分搜尋法所要搜尋的資料數列，要先排序才可行。
(0-2)要用二分搜尋法在給定的資料數列搜尋數字K，過程如下：
「 將K和「數列的中間數」比較，
如果二數相等，則在數列中找到有K，搜尋結束。
如果K比中間數大，則往「大的那一方」找，
如果K比中間數小，則往「小的那一方」找，
如果待尋「那一方」不存在則搜尋結束。」
不管往「大的那一方」或「小的那一方」搜尋皆採同上處理方式。
(1-1)在notepad輸入如下JS程式碼並存檔在桌面為bs01.htm
<script>
var a = [1, 13, 5, 26, 7 , 18 , 9];
function bsearch(k){
document.write("<hr>數字k="+k+"的搜尋結果如下：");
var L=0;
var R=a.length-1;
var M=(L+R)/2;
while (L<=R){
document.write("<br> L="+L+" a[L]="+a[L]+", R="+R+" a[R]="+a[R]+", M="+M+" a[M]="+a[M]+"");
if (a[M]==k) {
document.write("<br> 找到一筆匹配在 M="+ M + " a[M]="+a[M]);
break;
}
else{
if (k >a[M]) {
L=M+1;
document.write("<br> k="+k+" > a[M]="+a[M]+" 往大的那一半找 => L="+L+" R=" +R + "<br>");
}
else {
R=M-1;
document.write("<br> k="+k+" < a[M]="+a[M]+" 往小的那一半找 => L="+L+" R=" +R + "<br>");
}
}
M=(L+R)/2;
}
if (L>R) document.write(" <br> 因"+L+"=L > R="+R+" => [L,R]的數字區間不存在，故找不到k="+k);
}
a.sort(function(a, b){return a - b;});
document.write("二分搜尋法<br>待搜尋陣列a[]="+a);
var k= parseInt(prompt("請輸入k=","7"));
document.write("<HR>你輸入的k=" + k + "<br>");
bsearch(k);
</script>
(2) 用firefox開啟bs01.htm並輸入8，瀏覽結果如下：
二分搜尋法
待搜尋陣列a[]=1,5,7,9,13,18,26
你輸入的k=8
數字k=8的搜尋結果如下：
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=8 < a[M]=9 往小的那一半找 => L=0 R=2
L=0 a[L]=1, R=2 a[R]=7, M=1 a[M]=5
k=8 > a[M]=5 往大的那一半找 => L=2 R=2
L=2 a[L]=7, R=2 a[R]=7, M=2 a[M]=7
k=8 > a[M]=7 往大的那一半找 => L=3 R=2
因3=L > R=2 => [L,R]的數字區間不存在，故找不到k=8
(3)按f5鍵重新整理firefox中的bs01.htm並輸入7，瀏覽結果如下：
二分搜尋法
待搜尋陣列a[]=1,5,7,9,13,18,26
你輸入的k=7
數字k=7的搜尋結果如下：
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=7 < a[M]=9 往小的那一半找 => L=0 R=2
L=0 a[L]=1, R=2 a[R]=7, M=1 a[M]=5
k=7 > a[M]=5 往大的那一半找 => L=2 R=2
L=2 a[L]=7, R=2 a[R]=7, M=2 a[M]=7
找到一筆匹配在 M=2 a[M]=7
(3)
<script>
var a = [1, 5, 7 ,9,13, 18 , 26];
function bs(k){
document.write("<hr>搜尋"+k+"如下：");
var L=0;
var R=a.length-1;
var M=(L+R)/2;
while (L<=R){
if (a[M]==k) {
document.write("找到"+k+"在a["+ M+"]處" );
break;
}
else{
if (k >a[M]) L=M+1; else R=M-1;
}
M=(L+R)/2;
}
if (L>R) document.write(" <br> 找不到 "+k);
}
document.write("<hr>a[]="+a+ "：");
var k= parseInt(prompt("k=","7"));
bs(k);
</script>
(4)
a[]=1,5,7,9,13,18,26：
搜尋7如下：找到7在a[2]處
REF-1:20200102用JavaScript設計二分搜尋法bs01.htm |