Binary Search in Python
Binary search is a searching algorithm in computer science that finds the target value in a sorted list. This is considered to be the best searching algorithm on a sorted list of elements with the best time complexity of O(1) and the average time complexity of O(log n). The mid-value of the sorted list is selected and compared with the target value. After this comparison, any of the below three steps are performed based on the conditions.
1. If the target value is equal to the mid-value, we return the location of mid-value as the location of the target value.
2. If the target value is less than the mid-value, the whole process is repeated again with the high value as mid-1 and a new mid-value is selected from the new range of numbers.
3. If the target value is greater than the mid-value, the whole process is repeated again with the low value as mid+1 and a new mid-value is selected from the new range of numbers.
The whole process is repeated until the high value < low value.
In the beginning, the low value is the min value and the high value is the max value in the list.
Advantages of binary search,
1. It is simple and easy to understand.
2. If the number of elements in the list is doubled, only 1 extra step is needed to find the target value.
3. The time complexity of the algorithm is linear or pseudo-linear.
The Binary Search algorithm is implemented in Python and the whole code is shown below.
import random
numbers = []#Generating 100 random numbers between 0 and 500
for _ in range(100):
numbers.append(random.randint(0, 500))#Binary Search algorithm method
def binary_search(numebrs, target, low, high):
mid = (low + high) // 2 #Finding the mid location of the list
if low > high:
return -1 #Return -1 if element does not exist
if target == numbers[mid]:
return mid #Return the location of mid value is that is the element
elif target < numbers[mid]:
return binary_search(numbers, target, low, mid - 1) #Returning the left part of the list for searching
else:
return binary_search(numbers, target, mid + 1, high) #Returning the right part of the list for searchinglow = 0
high = len(numbers) - 1target = int(input('Enter target value: ')) #Value to be searchedposition = binary_search(numbers, target, low, high)
if position == -1:
print('Value not present in list')
else:
print('value present in location: ', position)
