Binary Search

Posted on

Method:

  • Binary search is an extremely time-efficient algorithm, especially in the face of large amounts of data, with a time complexity of log(n).
  • The main idea is to keep folding in half, removing half of the data volume for each search, until finally all the unqualified data are removed and only one qualified result remains.
    • Assuming that the target value is in the closed interval [l, r]. We will find the target value when l = r by reducing the length of the interval by half each time.

For Integer Numbers:

Idea:

  1. Begin with the mid element of the whole array as a search key.
  2. If the value of the search key is equal to the item then return an index of the search key.
  3. Or if the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
  4. Otherwise, narrow it to the upper half.
  5. Repeatedly check from the second point until the value is found or the interval is empty.

C++ Code for Version I:

  • When we divide the interval [l, r] into [l, mid] and [mid + 1, r], No need to add 1 when calculating mid, which means the update operation is r = mid or l = mid + 1;
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;
}

C++ Code for Version II:

  • When we divide the interval [l, r] into [l, mid – 1] and [mid, r]. To prevent dead loops, it is necessary to add 1 when calculating mid, which means the update operation is r = mid – 1 or l = mid;
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;
}

For Decimal Numbers:

  • We can assume r = l when r – l ≤ 10-6
  • Normally, add two to Exponential to avoid calculation errors.
    • To retain six decimal places, we can use r – l ≤ 10-8

C++ Code for Version III:

double bsearch_2(double l, double r)
{
    while (r - l > 1e-6) 
    //for (int i = 0; i < 100; i++)
    {
        double mid = (r + l) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    return l;
}

Reference: