JavaScript算法-二分查找

二分查找

定義:二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。

原理分析

定量1000規模需要查詢次數

1000 500 250 125 62 31 15 7 3 1 =>  最壞需要查詢10次

規模時間關系猜想:

 = 512   

 = 1024  

 = 1000?  

=  

 =

證明猜想: 

• 如果N正好是2的k次幂 如1024, 2048 ...

 ,共k+1項 即 

  成立

• 如果N不是2的k次幂

 , 共(k-1)+1=k項 即 

 成立

速度對比

1. 如果是普通周遊,查找1000個規模,最壞情況需要 1000 次.
2. 經過二分查找,最壞隻需要 10 次. 
3. 速度提升近100倍

算法實作

• 算法抽象

function bsearch (A, x)

A: 有序數組

x: 需要查找的元素

傳回1: x在A中的位置

傳回2: 不存在 -1

• 圖解算法

查找 66

1	2	3	4	5	6	7	8	9	10	11	數組鍵位
3	6	9	13	14	23	35	44	46	54	56	60	g= , l=0, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g= 5, l=6, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g=8 , l=9, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g=10, l=11, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g=11 , l=12, r=11

查找55

1	2	3	4	5	6	7	8	9	10	11	數組鍵位
3	6	9	13	14	23	35	44	46	54	56	60	g= , l=0, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g= 5, l=6, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g=8 , l=9, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g=10, l=9, r=9
3	6	9	13	14	23	35	44	46	54	56	60	g=9 , l=10, r=9

查找13

1	2	3	4	5	6	7	8	9	10	11	數組鍵位
3	6	9	13	14	23	35	44	46	54	56	60	g= , l=0, r=11
3	6	9	13	14	23	35	44	46	54	56	60	g= 5, l=0, r=4
3	6	9	13	14	23	35	44	46	54	56	60	g=2 , l=3, r=4
3	6	9	13	14	23	35	44	46	54	56	60	g=3, l=3, r=4

• 尋找循環不變式

循環前: l代表查找的左邊界 r代表查找的右邊界 guess代表r,l中間位置

循環後: l代表查找新的左邊界 r代表查找新的右邊界 guess重新計算 (r+l)/2向下取整

• 程式實作

function bsearch(A, x){
    let l = 0,           //初始查找左邊界
        r = A.length-1,  //初始查找右邊界
        guess            //猜想位置

    while(l <= r){
        guess = Math.floor((r+l)/2); // 循環不變式
     
        if(A[guess] == x) return guess
        else if (A[guess] > x) r = guess-1
        else l = guess+1
    }

    return -1;

}