二分查找模板

桃扇骨 2023-01-10 14:53 125阅读 0赞

[引用闫大佬的二分模板][Link 1]

二分模板一共有两个，分别适用于不同情况。  
算法思路：假设目标值在闭区间\[l, r\]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

**版本1**

当我们将区间 \[l, r\] 划分成 \[l, mid\] 和 \[mid + 1, r\] 时，其更新操作是 r = mid 或者 l = mid + 1 ，计算mid时不需要加1。

等价于

int a[] = { 1, 3, 5, 7, 9};
    lower_bound(a, a + 5, 1) - a; // 第一个大于等于1的元素是1，下标是0

C++ 代码模板：

第一种
    int bsearch_1(int l, int r)
    { 
         while (l < r)
         { 
             int mid = l + r >> 1;
             if (check(mid)) r = mid;
             else l = mid + 1;
         }
         return l;
     }
    
    int bsearch_1(int l, int r,int arr[],int NumberToFind)
    { 
        while (l < r)
        { 
            int mid = l + r >> 1;
            if (arr[mid] >= NumberToFind) r = mid;  //大于等于NumberToFind最小的那个数
            else l = mid + 1;
        }
        printf("%d",l);
        return l;
    }
    int main()
    { 
        int arr[5] = { 0,1,3,4,5};
        bsearch_1(0,4,arr,2);
    
        return 0;
    }
    
    bsearch_1(0,4,arr,2);
    这里寻找的是2， 元素不在数组里，则会找到从左往右数第一个 >= NumberToFind的元素位置，就是arr[2]
    bsearch_1(0,4,arr,-10);
    如果这里寻找-10,元素不在数组里，则会找到从左往右数第一个 >= NumberToFind的元素位置，就是arr[0]
    bsearch_1(0,4,arr,20);
    如果这里寻找20,元素不在数组里,会找到arr[4]

**版本2**

当我们将区间 \[l, r\] 划分成 \[l, mid - 1\] 和 \[mid, r\] 时，其更新操作是 r = mid - 1 或者 l = mid ，此时为了防止死循环，计算mid时需要加1。

C++ 代码模板：

第二种类
    
    int bsearch_2(int l, int r)
    { 
        while (l < r)
        { 
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    
    
    int bsearch_1(int l, int r,int arr[],int NumberToFind)
    { 
        while (l < r)
        { 
            int mid = l + r + 1>> 1;
            if (arr[mid] <= NumberToFind) l = mid;     //小于等于NumberToFind最大的那个数
            else r = mid - 1;
        }
        printf("%d",l);
        return l;
    }
    
    int main()
    { 
        int arr[5] = { 0,1,3,4,5};
        bsearch_1(0,4,arr,4);
    
        return 0;
    }
    
    
    则会找到第一个从右往左数 <= NumberToFind的元素位置!

C++还有一个二分函数

int a[] = { 1, 3, 5, 7, 9};
    upper_bound(a, a + 5, 1) - a// 第一个大于1的元素是3，下标是1

[Link 1]: https://www.acwing.com/blog/content/31/