【基础算法篇】二分

背景

二分排序我在大学学习的时候不以为意 以为这个很简单 直到看了y总的解释才知道我停留在很浅的理解上

介绍

二分程序虽然简单，但是如果写之前不考虑好想要查找的是什么，十有八九会是死循环或者查找错误，就算侥幸写对了也只是运气好而已。用二分去查找元素要求数组的有序性或者拥有类似于有序的性质，对本题而言，一个包含重复元素的有序序列，要求输出某元素出现的起始位置和终止位置

所以，需要写两个二分，一个需要找到>=x的第一个数，另一个需要找到<=x的最后一个数。

1. 查找<=x的最后一个位置(也就是寻找左区间)：

int SL(int l, int r, int x)
{
    while(l < r)
    &#123;
        int mid = (l + r) >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    &#125;
    return l;
&#125;

2. 查找>=x的第一个位置(也就是寻找右区间)：

int SR(int l, int r, int x)
{
    while(l < r)
    &#123;
        int mid = (l + r + 1) >> 1;
        if(a[mid] <= x) l = mid;
        else r = mid - 1;
    &#125;
    return r;
&#125;

三 、AC代码

 #include <iostream>

 using namespace std;
 const int N = 100010;
 int a[N];

 int SL(int l, int r, int x)
 &#123;
     while(l < r)
     &#123;
         int mid = (l + r) >> 1;
         if(a[mid] >= x) r = mid;
         else l = mid + 1;
     &#125;
     return l;
 &#125;

 int SR(int l, int r, int x)
 &#123;
     while(l < r)
     &#123;
         int mid = l + r + 1 >> 1;
         if(a[mid] <= x) l = mid;
         else r = mid - 1;
     &#125;
 &#125;

 int main()
 &#123;
     int n, m;
     scanf("%d%d", &n, &m);

     for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
     while (m -- )
     &#123;
         int x;
         scanf("%d", &x);

         int l = SL(0, n - 1, x);
         if(a[l] != x)
             printf("-1 -1\n");
         else
             printf("%d %d\n", l, SR(0, n - 1, x));
     &#125;
     return 0;
 &#125;

习题 数的三次方根

https://www.acwing.com/problem/content/792/

AC代码

#include <iostream>
#include<iomanip>
using namespace std;

int main()
&#123;
    double n;
    cin >> n;
    double l = -10000, r = 10000;
    while(r - l > 1e-7)
    &#123;
        double mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    &#125;
    cout << fixed << setprecision(6) << l;
    return 0;
&#125;