Codility - Lesson 14 Binary Search Algorithm

Source Link:
https://codility.com/programmers/lessons/14-binary_search_algorithm/

Some Notes:
The binary search is a simple and very useful algorithm whereby many linear algorithms can
be optimized to run in logarithmic time.

In a binary search we use the information that all the elements are sorted.

Let’s see how the number of candidates is reduced, for example for the value x = 31.



For every step of the algorithm we should remember the beginning and the end of the remaining
slice of the array (respectively, variables beg and end). 

The middle element of the slice can easily be calculated as mid = (beg+end) / 2.

14.1: Binary search in O(log n).
1 def binarySearch(A, x):
2 n = len(A)
3 beg = 0
4 end = n - 1
5 result = -1
6 while (beg <= end):
7 mid = (beg + end) / 2
8 if (A[mid] <= x):
9 beg = mid + 1
10 result = mid
11 else:
12 end = mid - 1
13 return result

In subsequent iterations the number of candidates is halved, so the time complexity is O(log n).