In Binary Search, we divide a collection of elements into two halves to reduce the comparisons for finding an element. But there is one condition, i.e., elements in the array are required to be sorted first. This article will explain the concept of Binary Search along with Binary Search Python implementation. There will be examples along with Python code snippets and outputs for better understanding.
Table of Contents
Binary Search Algorithm:
The Binary Search Algorithm finds an index of a particular element in the list. It is one of the fastest and most popular algorithms. The elements in the list must be sorted for Binary Search Algorithm to work.
Compared with Linear search, Binary Search is more efficient search algorithm in finding an element’s index as we don’t need to search each index of the list.
We can summarize the complete working of the Binary Search Algorithm in the following steps:
- In the sorted array, find the middle element.
- Compare x with the middle element.
- If x equals the middle element, then the middle index is returned. Otherwise, the x will be compared with the middle item.
- Else if x is greater than the middle item, then it will be compared to the right-side elements of the index.
- Else if x is less than the mid element, then x will be compared to only the left side elements of the index.
- We will choose either algorithm to run for the right half of the list or the left half of the list of items
Binary Search is an efficient algorithm. It has two methods for finding the position of elements. Let’s discuss this with the help of examples.
1. Recursive Method
The Recursive method follows the divide and conquer approach. In Recursive Binary Search, one function calls itself repeatedly until an element is found in the list.
Example:
def binary_search(array, low, high, x):
if high >= low:
mid = (high + low) // 2
if array[mid] == x:
return mid
elif array[mid] > x:
return binary_search(array, low, mid - 1, x)
else:
return binary_search(array, mid + 1, high, x)
else:
return -1
array = [ 2, 4, 6, 8, 20, 40, 60, 80]
x = 20
result = binary_search(array, 0, len(array)-1, x)
if result != -1:
print("The index of the Element is", str(result))
else:
print("This element is not present in your Array.")
Output:
2. Iterative Method
We use While Loop in the Iterative method to find the index position of an element. A set of statements will be repeated multiple times in Iterative implementation.
Example:
def binary_search(array, x):
low = 0
high = len(array) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if array[mid] < x:
low = mid + 1
elif array[mid] > x:
high = mid - 1
else:
return mid
return -1
array = [ 2, 4, 6, 8, 20, 40, 60, 80 ]
x = 20
result = binary_search(array, x)
if result != -1:
print("The index of the element is", str(result))
else:
print("We do not have this element in the Array.")
Output:
Complexity:
In concepts of Binary Search, we have two kinds of Binary Search Complexity.
- O(1): It is known as best case complexity when first comparison is equal to that item for we are searching.
- O(log n): It is called as average and worst case complexity as it takes quite long time with logarithmic time for searching item through a list.
Conclusion:
We discussed above, Binary Search is an effective technique to find the index of an element in list or an array. There were examples to differentiate recursive Binary Search and Iterative Binary Search. I hope it helped you in proper understanding
