二分查找

二分查找基本思路与模板

image

def binary_search(l , r): # 模板一：寻找右区间的左端点(上图红色部分)

    while l < r:
        mid = (l+r)//2 # 注意 l+r

        if check(mid): r = mid  // check(mid) 为true  mid对应的值>=target
        else: l = mid+1

def binary_search(l , r): # 模板二：寻找左区间的右端点（上图蓝色部分）

    while l < r:
        mid = (l+r+1)//2 # 注意 l+r+1

        if check(mid): l = mid // check(mid) 为true  mid对应的值<=target

        else: r = mid-1

大致可以分为寻找左边的最后一个（左区间的右端点）、右边的第一个（右区间的左端点）。

注意点：

//右区间的左端点  ，为什么是(l+r)/2
模板一： mid = (l+r)/2; r = mid; l = mid+1

//左区间的右端点 为什么是(l+r+1)/2
模板二：mid = (l+r+1)/2; l = mid; r = mid-1

在模板一情况下，
当区间收缩到[i,i+1]时
若 mid=（l+r+1）/2，即mid=(i+i+1+1)/2=i+1 那么check(mid)为true，则
r=mid=i+1,区间为[i，i+1]，则进入死循环。

在模板二情况下，
当区间收缩到[i,i+1]时，
若 mid= (l+r)/2, 即mid=(i+i+1)/2=i+1/2=i 那么check(mid)为true，则
l=mid=i ，区间为[i,i+1],进入死循环。

一个简单的示例：

const data=[1,2,4,6,6,7,8,9,9,9,9,23,56,88,100];

// 右区间的第一个数

function test1(num,data){
    

    let i=0;
    let j=data.length-1;

    while(i<j){

        let mid=(i+j)/2;
        
        if(check(data[mid],num)){
            j=mid;
        }else{
            i=i+1
        }
    }
    return i
}

function check(now,target){
    if(now>=target){
        return true;
    }else{
        return false;
    }
}

console.log("右区间",test1(9,data))

//左区间 最后一个数

function test2(num,data){
    let i=0;
    let j=data.length-1;

    while(i<j){

        let mid=(i+j+1)/2;
        
        if(data[mid]<=num){
            i=mid;
        }else{
            j=j-1
        }
    }
    return j
}


console.log("左区间：",test2(9,data))

参考

二分法