Write a Code to implement the binary search in Python
Binary Search
Implement binary search algorithm to find element in sorted list using Python
Searching is one of most common and important operations in computer science. There are various search algorithms available but binary search is one of most efficient algorithms for finding element in a sorted list. In this blog post, we will discuss the binary search algorithm how it works and how to implement it in Python.
What is Binary Search in Python?
Binary search is a searching algorithm used to find a specific element in a sorted list. It works by repeatedly dividing the search range in half until the desired element is found. The list must be sorted before performing a binary search. Below algorithm is very efficient and reduces search range by half at each step making it faster than linear search.
How does Binary Search in Python work?
The binary search algorithm works by following the below steps:
- Calculate middle element of list.
- If middle element is the target element then search is complete.
- If target element is less than the middle element search left half of the list.
- If target element is greater than the middle element search the right half of the list.
- Repeat step 1-4 until target element is found or the search range is empty.
Let’s take an example to understand how binary search in python works:
Suppose we have a sorted list [1, 3, 5, 7, 9, 11, 13, 15]. We want to find the index of element 5 using binary search.
The first step is to calculate middle element of list which is 7. Since 5 is less than 7 we search the left half of the list [1, 3, 5]. The middle element of the left half is 3. Since 5 is greater than 3 we will search right half of the left half[5]. The middle element of [5] is 5 which is target element. Hence the index of the target element is 2.
3 Ways to Implement the Binary Search in Python
Implementing Binary Search in Python
Now lets implement binary search algorithm in Python. We will write a function called binary_search that takes two arguments sorted list and target element and returns the index of the target element if it exists. If the target element is not present in the list the function will return -1.
def binary_search(arr, target):
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
The binary_search the function works as follows:
- We set the left pointer to the first element of list and the right pointer to the last element of the list.
- While left pointer is less than or equal to the right pointer we calculate middle index of the list.
- If middle element is the target element then we return index of that element.
- If middle element is less than the target element then we update the left pointer to mid + 1 since the target element must be in the right half of the list.
- If middle element is greater than the target element then we update the right pointer to mid – 1 since the target element must be in the left half of the list.
- If the target element is not found function will return -1.
Now, let’s test the binary_search function in Python on a sample list:
arr = [2, 4, 6, 8, 10, 12, 14, 16]
target = 10
result = binary_search(arr, target)
print(f"The index of {target} in the list is {result}.")
Output:
The index of 10 in the list is 4.
The output confirm that binary_search the function works correctly and returns the index of target element.
We can also test the binary_search function on some edge cases such as empty list or a list with single element.
# Test case 1: Empty list
arr = []
target = 10
result = binary_search(arr, target)
print(f"The index of {target} in the list is {result}.")
# Expected output: -1
# Test case 2: List with a single element
arr = [10]
target = 10
result = binary_search(arr, target)
print(f"The index of {target} in the list is {result}.")
# Expected output: 0
Output:
The index of 10 in the list is -1.
The index of 10 in the list is 0.
The output confirms that the binary_search function handles edge cases correctly and returns -1 if the list is empty or target element is not found.
Explore More Programming Challenges:
Conclusion
Binary search is efficient search algorithm that reduce search range by half at each step.It works best on sorted lists and can quickly find index of the target element. In this blog post we have discussed the binary search algorithm and its implementation in Python.We also tested the binary_search function on some sample and edge cases to confirm it’s correctness.