Home

binary search

Exercise

Difficulty : Easy

Statement

There are an array $A$ of length $N$ sorted in non-descending order (that is, $A_i \le A_{i + 1}$) and a value $X$. Find the index of $X$ within $A$ (indices start from 0). If $X$ is not in the array, return $-1$.

Input

Example

Input

$A_i$ 1 4 8 10
$i$ 0 1 2 3

Output

The output should be 2 since we can make this new array :

$A_i$ 1 4 8 10
$i$ 0 1 2 3

Follow-up

Return the index where $X$ must be within $A$.

Example

Input
$A_i$ 1 4 8 10
$i$ 0 1 2 3
Output

The output should be 2 since we can make this new array :

$A_i$ 1 4 7 8 10
$i$ 0 1 2 3 4

Solution

Suppose $X$ is in the array. Maintain two values, $l$ and $r$ representing an interval where $X$ is (e.g. $X \in [l, r]$).

$A_i$ 1 4 8 10
$i$ 0 1 2 3
l/r l     r

Note that $r$ is excluded in the source code, that is, the interval is $[l, r - 1]$

While this interval has at least two values, we have to minimize it. Let mid be the middle value, mid = $\lfloor \frac {l + r} 2 \rfloor$.

To minimize the interval, we have to choose to keep either $[mid + 1, r]$ or $[l, mid - 1]$.

Code

int binary_search(const vector<int> &array, int val) {
    // val is within [l, r) (if val is in the array)
    int l = 0;
    int r = array.size();

    // While the range [l, r) is not empty
    while (l < r) {
        int mid = l + (r - l) / 2;

        if (array[mid] == val) {
            // Found
            return mid;
        } else if (array[mid] < val) {
            // val is not before l, so val is within [mid + 1, r)
            l = mid + 1;
        } else /* array[mid] > val */ {
            // val is not after r, so val is within [l, mid)
            r = mid;
        }
    }

    // Not found, val should be at index l
    return -1;
}
Full code