Understanding of binary search

Common binary template ：

Template I , The interval is left closed and right closed , That is, the search interval is [l,r]

int binary_search(int l, int r, int a[], int x)  // The return value is the element x In the array a Position in （ Subscript ）
{
    int mid = 0;
    while(l <= r)
    {
        mid = (l+r) >> 1;
        if(a[mid] == x)
            return mid;
        if(a[mid] < x)
            l = mid+1;
        else
            r = mid-1;
    }
    return -1;
}

Template II , The interval is left closed and right open , That is, the search interval is [l,r), Foreigners like to play this , And then the whole STL Basically, they are closed on the left and open on the right .

int binary_search(int l, int r, int a[], int x)
{
    int mid = 0;
    while(l < r)
    {
        mid = (l+r) >> 1;
        if(a[mid] == x)
            return mid;
        if(a[mid] < x)
            l = mid+1;
        else
            r = mid ;
    }
    return -1;
}

Notice the difference between the two templates , If it is left closed and right closed ,while The loop should be able to l == r Of , Then update r When you are, you should r The assignment is mid-1, Because the search subinterval should also be left closed and right closed （ because mid At the time of this search, I have already checked , So when dividing subintervals mid Should not be in the interval ）.

If the template is closed on the left and opened on the right , When updating r To assign as mid, In this way, we can ensure that the subinterval is also left closed and right open .

l The update is always mid+1, After all, both templates are left closed intervals .