This article deals with the binary search algorithm implementation in Python programming language.
Binary search is an improvement to linear search. Binary search requires the searched list to be an ordered list, i.e. the list items should be sorted in ascending order (increasing order).
Binary Search
This algorithm is a good example of Divide and Conquer strategy.
– This search algorithm doesn’t go on searching in a sequential manner like in linear search.
– It directly moves to the middle item and compares it with the searched item/value.
– If the compared item is same as the searched item then the algorithm terminates.Otherwise,
– If the compared item is greater than the searched item then we can skip entire second half (right half) of the list of the compared item.
– If the compared item is less than the searched item then we can skip entire first half (left half) of the list from the compared item.– After that, we repeat the above process again for one of the halves of the list.
– This algorithm runs until the sub-list / sub-array size is reduced to zero, i.e. until there is no possibility of dividing the list into two halves.
Implementation in Python
The output result will be the position of the searched element/item in the list. In programming, the counting of a list or array starts from 0. So, the first element of a list is said to be in 0th position. The second element of the list is said to be in the 1st position and so on.
In the below code, the number 44 is the seventh element of the list. So, it is said to be in the 6th position of the list (as the list position counting starts from zero).
def binary_search(item_list, item):
first_position = 0
last_position = len(item_list) - 1
while first_position <= last_position: mid_point = (first_position + last_position) // 2 # // = floor division, removes decimal from result if item_list[mid_point] == item: return mid_point else: if item_list[mid_point] > item:
last_position = mid_point - 1 # skipping right half
else:
first_position = mid_point + 1 # skipping left half
return False
item_list = [1, 2, 4, 8, 23, 25, 44, 78, 89, 100]
item = 44
print (binary_search(item_list, item))
# Output:
# 6
Printing some Message on each Iteration
It’s the same implementation but we print some output message on each iteration of the loop. This is useful to see what’s going on inside the loop.
def binary_search(item_list, item):
first_position = 0
last_position = len(item_list) - 1
print ('First position: ' + str(first_position))
print ('Last position: ' + str(last_position))
while first_position <= last_position: mid_point = (first_position + last_position) // 2 # // = floor division, removes decimal from result print ('Mid point: {mid_point}'.format(mid_point=mid_point)) if item_list[mid_point] == item: return mid_point else: if item_list[mid_point] > item:
last_position = mid_point - 1 # skipping right half
else:
first_position = mid_point + 1 # skipping left half
print ('First position: {}'.format(first_position))
print ('Last position: %d' % (last_position))
return False
item_list = [1, 2, 4, 8, 23, 25, 44, 78, 89, 100]
item = 44
print (binary_search(item_list, item))
# Output:
# First position: 0
# Last position: 9
# Mid point: 4
# First position: 5
# Last position: 9
# Mid point: 7
# First position: 5
# Last position: 6
# Mid point: 5
# First position: 6
# Last position: 6
# Mid point: 6
# 6
item_list = [1, 2, 4, 8, 23, 25, 44, 78, 89, 100]
item = 4
print (binary_search(item_list, item))
# Output:
# First position: 0
# Last position: 9
# Mid point: 4
# First position: 0
# Last position: 3
# Mid point: 1
# First position: 2
# Last position: 3
# Mid point: 2
# 2
Time Complexity
Time complexity is related to the number of operations occurring in an algorithm. In binary search, the crucial operation is the comparison of the data.
In binary search algorithm, there are two comparisons in each iteration:
1. Checking if the item in the list is equal to the searched item (
if item_list[mid_point] == item)
2. Checking if the item in the list is greater than (or less than) the searched item (if item_list[mid_point] > item)
Suppose there are n items in the list.
1st iteration will reduce the items on the list to n/2
2nd iteration will reduce the items on the list to n/4
3rd iteration will reduce the items on the list to n/8
and so on
If n = 1, i.e. there is only one item in the list, then
Time complexity: T(n) = 1
If n > 1, i.e. there are more than 1 item in the list, then the binary search algorithm works in the following manner:
1st iteration:
$latex
T(n) = T(\frac{n}{2}) + 2
$
where,
2= number of comparisons in each iteration
T(n/2)= remaining time complexity because each iteration will reduce the item list to half of its size
2nd iteration:
$latex T(\frac{n}{2}) = T(\frac{n}{4}) + 2 + 2 $
3rd iteration:
$latex T(\frac{n}{4}) = T(\frac{n}{8}) + 2 + 2 + 2 $
…
…
…
kth iteration:
$latex T(\frac{n}{2^k}) + 2*k $
We can assume that,
$latex n = 2^k $,
Putting log_2 on both sides:
$latex log_2 n = log_2 (2^k) $
$latex log_2 n = k log_2 2 $
$latex log_2 n = k $
And,
$latex T(\frac{n}{2^k}) = T(\frac{2^k}{2^k}) = T(1) = 1 $
Therefore,
Time Complexity:
$latex = T(\frac{n}{2^k}) + 2*k $
$latex = 1 + 2k $
$latex = 1 + 2 log n $
f(n) = O(logn)
Explaining binary search time complexity in another way
In Binary search, we have to divide the list into half, i.e. divide by 2. And, we go on dividing the sub-list until we find the searched item.
Time complexity (worst case) can be defined by how many times do you have to divide the list until you have 1 item remaining on the list.
Suppose, there are n items in the list and you have to divide the list by k times to get 1 item remaining on the list.
This can be mathematically represented as:
$latex n/2^k = 1 $
$latex n = 2^k $
$latex 2^k = n $
putting log_2 on both sides:
$latex log_2 (2^k) = log_2 n $
$latex k * log_2 2 = log_2 n $
$latex k * 1 = log_2 n $
$latex k = log_2 n $
This means that you have to divide the list by log_2n times to get single item remaining on the list.
Hence, time complexity
O(n) = log n
Hope this helps. Thanks.