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))
