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;

}