Hello Codeforces!

This post will be about one of the programming topics called binary search

Some example:

Given a sorted array a1 ≤ a2 ≤ . . . ≤ an of n numbers. Need to find a position numbers x, i.e., i such that ai = x.

A naive solution would be to go through the array and check each number.

--------------------------------------------------------------------

--------------------------------------------------------------------

Time complexity O(N)

Let's try to speed up the algorithm.

We initialize the response area, i.e. such an interval [l, r] on which the answer is (i ∈ [l, r]). In at the very beginning l = 1, r = n.

Then we have 2 cases:

• l = r. And if a[l] = x, then we have found the answer, otherwise the element does not exist in the array.

• l < r. Let's divide our interval into two parts, i.e.

let's take this m = (l+r)/2 and divide the interval into 2 parts [l, m] and [m + 1, r].

• If a[m] < x, then x is definitely not in the left half because all the elements are smaller X. That is. l := m + 1.

• Otherwise, x is in the left half and you can discard the right half. That is. r := m.

--------------------------------------------------------------------

--------------------------------------------------------------------

Time complexity: O(log(N))

I hope you found this blog useful. Good luck!