樹心幽徑

« 20200619用JavaScript來編寫氣泡排序法及選擇排序法程式 | Main

20200701用JavaScript設計二分搜尋法
2020/06/30,21:55

(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

迴響

 
Accessible and Valid XHTML 1.0 Strict and CSS Powered by LifeType