• 周四. 12月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

二分查找

admin

11月 28, 2021

二分查找的本质是可以在有序的数列中,通过二分一个中间值进行探测,可以一次排除掉一半的数据,最后要么找到需要的数据,要么排除掉所有的数据。时间复杂度只有logN

bool binarySearch(int l, int r, int []arr, int value) {
    while(l<=r) {
     int mid = (l + r) / 2;
        if (arr[mid] < value) l = mid + 1;
        else if (arr[mid] > value) r = mid - 1;
        else return true;      
    }  
    // 没有找到
    return false;
}  

View Code

还有一种情况,比如说需要寻找在数列中不大于value的最大值,可以在上面二分的基础上增加一个index记录边界值,代码入下:

int binarySearch(int l, int r, int []arr, int value) {
    int index = -1;
    while(l<=r) {
     int mid = (l + r) / 2;
        if (arr[mid] <= value) l = mid + 1, index = mid;
        else if (arr[mid] > value) r = mid - 1;   
    }  
    return index;
}  

 经过不断排除和试探,最后mid肯定会取到边界值上面去

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注