Last Updated on June 28, 2023 by Prepbytes
Binary search is a fundamental algorithm used to efficiently search for a specific element in a sorted list or array. It follows a divide-and-conquer approach, reducing the search space by half with each iteration. Implementing a binary search program in Python allows us to take advantage of the language’s simplicity and powerful built-in functions.
In this article, we will explore how to write a binary search program in Python. We will discuss the underlying logic of the binary search algorithm and walk through the step-by-step process of implementing it in Python. By leveraging Python’s intuitive syntax and array manipulation capabilities, we can create a concise and effective binary search program.
What is Binary Search in Python?
Binary search is a search algorithm used to find the position of a target element within a sorted list or array. It follows a divide-and-conquer strategy, repeatedly dividing the search space in half until the target element is found or determined to be absent.
In Python, binary search can be implemented using a recursive or iterative approach. The algorithm compares the target element with the middle element of the sorted list and adjusts the search space accordingly. If the middle element is equal to the target, the search is successful. Otherwise, if the target is smaller, the search continues in the lower half of the list, and if the target is larger, the search proceeds in the upper half.
Binary search is highly efficient, as it eliminates half of the remaining search space at each iteration, resulting in a time complexity of O(log n), where n is the number of elements in the list. This makes it particularly useful for large datasets where linear search would be impractical.
Binary search is a widely used algorithm in various applications such as searching in databases, finding elements in sorted arrays, and determining insertion points in ordered collections.
Implementing binary search in Python allows for quick and effective searching within sorted lists or arrays, providing a valuable tool for solving search-related problems in programming.
Example of Binary Search in Python
Let’s consider an example to understand binary search in Python better. Suppose we have a textbook with 500 pages, and we want to find page number 343 within it. We can apply the binary search algorithm to efficiently locate the target page.
We start by examining the middle page, which in this case is page 250. Since 343 is greater than 250, we can discard the first half of the book as we no longer need it. Next, we move to the middle of the remaining pages, which is page 375. As 343 is less than 375, we can discard the pages after page 375.
Now, we have narrowed down our search space to pages 251 to 374. We repeat the same process by identifying the middle page, which is page 312. Comparing 343 with 312, we determine that the target page is greater. Consequently, we update our starting point to page 313 and the ending point to page 374.
Finally, we calculate the middle page, which is page 343. By checking if the target page is equal to the middle page, we confirm that we have found the desired page within the textbook.
This example illustrates the iterative process of binary search, where the search space is continuously divided in half based on comparisons with the middle element. By leveraging this approach, binary search significantly reduces the number of comparisons required to find a target element within a sorted collection, resulting in an efficient search algorithm.
Dry Run of Binary Search
Now that you understand the basic operation of the binary search algorithm, let’s look at an example with a process flow diagram for each run.
Let’s say we have an array with the elements listed below. In the list, we look for element 90, which is our goal.
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 the target while setting the starting and finishing points. The midpoint is then moved depending on whether the target is positioned greater or less than the midpoint. If the target is located at the midpoint, it returns the mid; otherwise, if start exceeds end, it returns -1.
Analysis of Code
Let’s look at the analysis of the code we wrote now that we have a general understanding of how to carry out a binary search in Python. In the worst scenario, it takes O(logn) time, but the space complexity is O(1), or constant time, because we don’t need any extra space and instead carry out the operations to locate the target on the actual list.
Time Complexity: O(logn)
Space Complexity: O(1)
The middle index in the first run has a decent chance of containing the required target value, therefore the best case complexity stays at O(1). With this, the analysis of Python code for binary search methods is complete
Conclusion
In conclusion, implementing a binary search program in Python provides an efficient and effective way to search for specific elements within a sorted list or array. By following the divide-and-conquer approach, binary search significantly reduces the search space with each iteration, leading to faster search times compared to linear search algorithms.
Python’s simplicity and powerful built-in functions make it an ideal language for implementing binary search. The concise syntax and array manipulation capabilities allow for a clean and straightforward implementation of the algorithm. Understanding and mastering binary search in Python is a valuable skill for any programmer, as it can be applied to a wide range of search-related problems.
By utilizing binary search in Python, you can improve the efficiency of your code, especially when dealing with large datasets or sorted collections. The logarithmic time complexity of binary search (O(log n)) ensures that even for massive data sets, the search operation can be performed quickly and effectively.
Frequently Asked Questions
Q1: Can binary search be used on unsorted data?
No, binary search requires the data to be sorted in ascending or descending order. If the data is unsorted, binary search will not yield correct results.
Q2: What is the time complexity of binary search in Python?
The time complexity of binary search is O(log n), where n is the number of elements in the sorted list or array. This logarithmic time complexity allows for efficient searching, even with large data sets.
Q3: Can binary search be applied to other data structures apart from lists or arrays?
Binary search is primarily used for searching within sorted lists or arrays. However, with appropriate adaptations and data structure designs, binary search can be applied to other structures such as binary trees or sorted linked lists.
Q4: How does binary search handle duplicate elements in the list or array?
Binary search can be modified to handle duplicate elements in different ways. It can either return the index of the first occurrence of the target element or implement a more advanced algorithm to handle duplicate elements separately.
Q5: When should I use binary search instead of linear search?
Binary search should be used when the data is sorted and the search operations need to be performed repeatedly. Linear search is more suitable for unsorted data or cases where the data set is small.