樹心幽徑

« 20200120設計可連線LAMP-MYSQL資料庫伺服器並新增資料庫、資料表、資料錄的PHP程式(c1.php) | Main | 20200106用GIMP製作有透明背景的動物圖png檔並在HTML網頁中呈現。 »

20200102用JavaScript設計二分搜尋法bs01.htm
2020/01/02,20:53

REF:20191122用DevC++來編寫循序搜尋法與二分搜尋法程式

 

(1-1)在notepad輸入如下JS程式碼並存檔在桌面為bs01.htm

<script>
var a = [1, 13, 5, 26, 7 , 18 , 9];
a.sort(function(a, b){return a - b;});
document.write("二分搜尋法<br>待搜尋陣列a[]="+a);

bsearch(1);
bsearch(4);
bsearch(18);
bsearch(26);


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);
}

</script>

(2) 用firefox開啟bs01.htm,瀏覽結果如下:

二分搜尋法
待搜尋陣列a[]=1,5,7,9,13,18,26


數字k=1的搜尋結果如下:
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=1 < a[M]=9 往小的那一半找 => L=0 R=2

L=0 a[L]=1, R=2 a[R]=7, M=1 a[M]=5
k=1 < a[M]=5 往小的那一半找 => L=0 R=0

L=0 a[L]=1, R=0 a[R]=1, M=0 a[M]=1
找到一筆匹配在 M=0 a[M]=1


數字k=4的搜尋結果如下:
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=4 < a[M]=9 往小的那一半找 => L=0 R=2

L=0 a[L]=1, R=2 a[R]=7, M=1 a[M]=5
k=4 < a[M]=5 往小的那一半找 => L=0 R=0

L=0 a[L]=1, R=0 a[R]=1, M=0 a[M]=1
k=4 > a[M]=1 往大的那一半找 => L=1 R=0

因1=L > R=0 => [L,R]的數字區間不存在,故找不到k=4


數字k=18的搜尋結果如下:
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=18 > a[M]=9 往大的那一半找 => L=4 R=6

L=4 a[L]=13, R=6 a[R]=26, M=5 a[M]=18
找到一筆匹配在 M=5 a[M]=18


數字k=26的搜尋結果如下:
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=26 > a[M]=9 往大的那一半找 => L=4 R=6

L=4 a[L]=13, R=6 a[R]=26, M=5 a[M]=18
k=26 > a[M]=18 往大的那一半找 => L=6 R=6

L=6 a[L]=26, R=6 a[R]=26, M=6 a[M]=26
找到一筆匹配在 M=6 a[M]=26

 

(2-1)在notepad輸入如下JS程式碼並存檔在桌面為bs02.htm

<script>
var a = [1, 13, 5, 26, 7 , 18 , 9];
for (i=0;i<10000;i++) a.push(rand(30000));

a.sort(function(a, b){return a - b;});
document.write("二分搜尋法<br>待搜尋陣列a[]="+a);

bsearch(111);
bsearch(444);
bsearch(1818);
bsearch(2626);

function rand(r){
 var x=Math.random()*r;
 var y=parseInt(x);
 while (a.indexOf(y) >=0) {
    x=Math.random()*r;
    y=parseInt(x);
    }
 return y;
}

function bsearch(k){
    document.write("<hr>數字k="+k+"的搜尋結果如下:");
    var L=0;
    var R=a.length-1;
    var M=parseInt((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(" 往大的那一半找 ");
                    }
                else {
                    R=M-1;
                    document.write(" 往小的那一半找 ");
                    }
            }
            M=parseInt((L+R)/2);
        }
       if (L>R) document.write("故找不到"+k);
}

</script>

 

(4)用firefox開啟bs02.htm,瀏覽結果如下:

數字k=111的搜尋結果如下:
L=0 a[L]=0, R=10006 a[R]=29999, M=5003 a[M]=14852 往小的那一半找
L=0 a[L]=0, R=5002 a[R]=14850, M=2501 a[M]=7440 往小的那一半找
L=0 a[L]=0, R=2500 a[R]=7437, M=1250 a[M]=3645 往小的那一半找
L=0 a[L]=0, R=1249 a[R]=3644, M=624 a[M]=1808 往小的那一半找
L=0 a[L]=0, R=623 a[R]=1797, M=311 a[M]=868 往小的那一半找
L=0 a[L]=0, R=310 a[R]=866, M=155 a[M]=445 往小的那一半找
L=0 a[L]=0, R=154 a[R]=444, M=77 a[M]=201 往小的那一半找
L=0 a[L]=0, R=76 a[R]=199, M=38 a[M]=87 往大的那一半找
L=39 a[L]=90, R=76 a[R]=199, M=57 a[M]=145 往小的那一半找
L=39 a[L]=90, R=56 a[R]=140, M=47 a[M]=117 往小的那一半找
L=39 a[L]=90, R=46 a[R]=114, M=42 a[M]=104 往大的那一半找
L=43 a[L]=109, R=46 a[R]=114, M=44 a[M]=110 往大的那一半找
L=45 a[L]=111, R=46 a[R]=114, M=45 a[M]=111
找到一筆匹配在 M=45 a[M]=111


數字k=444的搜尋結果如下:
L=0 a[L]=0, R=10006 a[R]=29999, M=5003 a[M]=14852 往小的那一半找
L=0 a[L]=0, R=5002 a[R]=14850, M=2501 a[M]=7440 往小的那一半找
L=0 a[L]=0, R=2500 a[R]=7437, M=1250 a[M]=3645 往小的那一半找
L=0 a[L]=0, R=1249 a[R]=3644, M=624 a[M]=1808 往小的那一半找
L=0 a[L]=0, R=623 a[R]=1797, M=311 a[M]=868 往小的那一半找
L=0 a[L]=0, R=310 a[R]=866, M=155 a[M]=445 往小的那一半找
L=0 a[L]=0, R=154 a[R]=444, M=77 a[M]=201 往大的那一半找
L=78 a[L]=207, R=154 a[R]=444, M=116 a[M]=320 往大的那一半找
L=117 a[L]=321, R=154 a[R]=444, M=135 a[M]=372 往大的那一半找
L=136 a[L]=376, R=154 a[R]=444, M=145 a[M]=415 往大的那一半找
L=146 a[L]=420, R=154 a[R]=444, M=150 a[M]=433 往大的那一半找
L=151 a[L]=435, R=154 a[R]=444, M=152 a[M]=437 往大的那一半找
L=153 a[L]=441, R=154 a[R]=444, M=153 a[M]=441 往大的那一半找
L=154 a[L]=444, R=154 a[R]=444, M=154 a[M]=444
找到一筆匹配在 M=154 a[M]=444


數字k=1818的搜尋結果如下:
L=0 a[L]=0, R=10006 a[R]=29999, M=5003 a[M]=14852 往小的那一半找
L=0 a[L]=0, R=5002 a[R]=14850, M=2501 a[M]=7440 往小的那一半找
L=0 a[L]=0, R=2500 a[R]=7437, M=1250 a[M]=3645 往小的那一半找
L=0 a[L]=0, R=1249 a[R]=3644, M=624 a[M]=1808 往大的那一半找
L=625 a[L]=1812, R=1249 a[R]=3644, M=937 a[M]=2714 往小的那一半找
L=625 a[L]=1812, R=936 a[R]=2712, M=780 a[M]=2233 往小的那一半找
L=625 a[L]=1812, R=779 a[R]=2230, M=702 a[M]=2031 往小的那一半找
L=625 a[L]=1812, R=701 a[R]=2022, M=663 a[M]=1922 往小的那一半找
L=625 a[L]=1812, R=662 a[R]=1920, M=643 a[M]=1860 往小的那一半找
L=625 a[L]=1812, R=642 a[R]=1859, M=633 a[M]=1834 往小的那一半找
L=625 a[L]=1812, R=632 a[R]=1833, M=628 a[M]=1817 往大的那一半找
L=629 a[L]=1821, R=632 a[R]=1833, M=630 a[M]=1822 往小的那一半找
L=629 a[L]=1821, R=629 a[R]=1821, M=629 a[M]=1821 往小的那一半找 故找不到1818


數字k=2626的搜尋結果如下:
L=0 a[L]=0, R=10006 a[R]=29999, M=5003 a[M]=14852 往小的那一半找
L=0 a[L]=0, R=5002 a[R]=14850, M=2501 a[M]=7440 往小的那一半找
L=0 a[L]=0, R=2500 a[R]=7437, M=1250 a[M]=3645 往小的那一半找
L=0 a[L]=0, R=1249 a[R]=3644, M=624 a[M]=1808 往大的那一半找
L=625 a[L]=1812, R=1249 a[R]=3644, M=937 a[M]=2714 往小的那一半找
L=625 a[L]=1812, R=936 a[R]=2712, M=780 a[M]=2233 往大的那一半找
L=781 a[L]=2234, R=936 a[R]=2712, M=858 a[M]=2486 往大的那一半找
L=859 a[L]=2489, R=936 a[R]=2712, M=897 a[M]=2610 往大的那一半找
L=898 a[L]=2611, R=936 a[R]=2712, M=917 a[M]=2668 往小的那一半找
L=898 a[L]=2611, R=916 a[R]=2665, M=907 a[M]=2648 往小的那一半找
L=898 a[L]=2611, R=906 a[R]=2642, M=902 a[M]=2627 往小的那一半找
L=898 a[L]=2611, R=901 a[R]=2626, M=899 a[M]=2616 往大的那一半找
L=900 a[L]=2623, R=901 a[R]=2626, M=900 a[M]=2623 往大的那一半找
L=901 a[L]=2626, R=901 a[R]=2626, M=901 a[M]=2626
找到一筆匹配在 M=901 a[M]=2626


迴響

 
Accessible and Valid XHTML 1.0 Strict and CSS Powered by LifeType