Binary Search is an important searching technique that is used to find target in fewer iterations in comparison to the linear search approach. Binary search is applicable only on sorted lists unlike linear search that works on either of the cases, sorted or unsorted.
What is Binary Search in Python?
Binary Search is a fast and efficient algorithm that looks for the target depending on the element at the middle of the two different indices, initially at index 0 and index n-1 where n is the total number of elements present in the list. It performs the search operation in logarithmic time in the worst case that is an improvement over the linear search time or for linear search but it must only be performed on a sorted array being inefficient for an unsorted list.
Example of Binary Search in Python
We can relate it with a an example of a textbook that has pages printed on it, Suppose we want to find target page 343 in a 500 page book, we move the middle but find that 343 is greater than 250, hence, tore apart the first 250 pages as we no longer require them, again we move the middle to 375 in our 500 page book as the average of 251 and 500 remains at 375, in result we find out that 343 is lesser than 375. Repeating the same step, we tore apart the pages after page no. 375.
The start is pointing at Page No. 251 and the end of the text book at Page No. 374, the middle of both the number turns out to be 312, which equals less than 343. Thus, placing our starting point at Page No. 313 and ending at Page No. 374, the middle is calculated to be 343, checking if the target is equal, we found out it is indeed equal to the target.
Dry Run of Binary Search
Having a clarity over the concept on how the binary search algorithm works, let us look at an example with a visualized process for each pass in the algorithm.
Suppose, we have an array with following elements. We look for our target element 90 in the list.
First Iteration:
We find the middle of the list, which is calculated as (0+5)//2 = 2, therefore we set our middle to 2.
We notice that 40 at the middle is less than our target, so place the start at mid+1 and start becomes 3.
Second Iteration:
Finding our new mid position, it is (3+5)//2 = 4 for now.
Again, we check if the element at mid is equal to target, only to find out it is lesser than target. We move the start pointer to mid+1.
Third Iteration:
Our start will be at 5 and end is already at 5, so our mid will be (5+5)//2 = 10 for now.
Our mid will be the same for this borderline condition on binary search and on checking the condition for search, we can find that the element at the last index is equal to target. I.e. 90
Algorithm for Binary Search in Python
As we have covered the conceptual and dry run part in this binary search python article, let us look at the algorithm to implement binary search in python. Here is the flowchart and algorithm for binary search to solidify the understanding.
Flowchart for Binary Search:
Algorithm for Binary Search:
- Find the middle element by dividing the sum of start index and end index by 2.
- If target equals the element at mid, return mid
- Else if element at mid is lesser than target, set start as mid+1
- Else if element at mid is greater than target, set end as mid-1
- Repeat the process until the element is found, return -1 if start is greater than end.
Recursive Code For Binary Search in Python
Let us look at the binary search python code using the recursive approach with explanation of the code.
def binary_search(arr,start,end,target):
mid = (start+end)//2
if start > end:
return -1
if arr[mid] < target:
return binary_search(arr, mid+1, end, target)
elif arr[mid] > target:
return binary_search(arr, start, mid-1, target)
elif arr[mid] == target:
return mid
arr = [20,30,40,60,80,90]
ans = binary_search(arr,0,len(arr)-1 ,20)
if ans == -1:
print("Target Not Found")
else:
print("Target found at index",ans) Explanation:
List named arr is passed with the starting and ending position as argument in the called function, the recursive function takes care of the binary search condition and call itself if the elements at mid are lesser or greater else, it returns the mid if target is found at mid or else it returns -1 if start exceeds the value of end.
Iterative Code For Binary Search in Python
Let us look at the binary search python code using the iterative approach with explanation of the code.
def binary_search(arr, target):
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
current = arr[mid]
if current == target:
return mid
if current > target:
end = mid - 1
else:
start = mid + 1
return -1
arr = [20,30,40,60,80,90]
ans = binary_search(arr,80)
if ans == -1:
print("Target Not Found")
else:
print("Target found at index",ans) Explanation:
Similar to the recursive approach, we pass the list and target and set the starting and ending points, the mid is moved as per the positioning of the target whether it is lesser than mid or greater. It returns the mid if target is found at mid or else it returns -1 if start exceeds the value of end.
Analysis of Code
Now that we have some idea of performing a binary search in python, let us look at the analysis of the code we wrote. It has a time complexity of O(logn) in the worst case while the space complexity is O(1) or constant time as we don’t take any extra space, rather perform the operations to find the target on the actual list.
Time Complexity: O(logn)
Space Complexity: O(1)
However, the best case complexity remains at O(1) as there is a fair chance that the middle index in the first pass contains the required target value. With this we are done with the study of algorithms for binary search python code.
Conclusion
In this article, we started with binary search and learnt it using a real-world example of a text book and dry run. Later in this article focused on binary search in python, we got to know the algorithm, solved binary search in python using recursive and iterative approach. We hope you liked this article and hope to see you again at PrepBytes with another informative article soon.
Frequently Asked Questions
1. What is binary search in Data structures?
Binary search is a fast and useful searching algorithm for finding an item from a sorted list of items. It works by dividing the lookup size to reach the target.
2. How does binary search work?
Binary search works by dividing the sorted list of items into two halves and checking which half the desired item is in. This process is repeated until either the item is found or the search interval is empty.
3. What are the advantages of using binary search?
Binary search is much faster than linear search for lists consisting of large items. It has a time complexity of O(log n), where n is the number of items in the list, which is much better than the O(n) time complexity of linear search.
4. Can binary search be implemented in python?
Binary search can be implemented in many programming languages, but the basic algorithm remains the same with this article focusing on binary search in python.
5. When should binary search be used instead of linear search?
When the list is already sorted then binary search is the most optimum option to search in the list as it provides logarithmic time complexity unlike linear search that has worst case complexity of O(N).