The main idea is to maintain an interval $[l, r]$ that still may contain the answer, repeatedly split it into two halves, and discard the half where the answer cannot be.

Basic Binary Search

We now describe a standard iterative binary search that returns an index $i$ such that a[i] = x, or -1 if $x$ is not present.

At the beginning, the answer, if it exists, must lie in the interval:

[l, r] = [1, n]

Then we repeat the following process.

Case 1: $l = r$

The interval contains only one position.

If $a_l = x$ , then we have found the answer.
Otherwise, the value $x$ does not appear in the array.

Case 2: $l < r$

We split the interval into two parts.

Let

m = \left\lfloor \frac{l + r}{2} \right\rfloor

Then the interval is divided into:

$[l, m]$
$[m+1, r]$

Now there are two possibilities:

If $a_m < x$ , then $x$ cannot be in the left half, because all elements there are at most $a_m$ and therefore smaller than $x$ .
So we set:

l := m + 1

Otherwise, the answer may still be in the left half, so we discard the right half and set:

r := m

Implementation

int find_linear(int x) {
    for (int i = 1; i <= n; i++) {
        if (a[i] == x) {
            return i;
        }
    }
    return -1; // if x does not exist in the array
}

int binary_search_any(int x) {
    int l = 1;
    int r = n;

    while (l < r) {
        int m = (l + r) / 2;
        if (a[m] < x) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    if (a[l] == x) {
        return l;
    }
    return -1;
}

Ikkilik qidiruv

Introduction

Required Problems

External Problems

Basic Binary Search

Case 1: l=rl = rl=r

Case 2: l<rl < rl<r

Implementation

Case 1: $l = r$

Case 2: $l < r$