Binary search is a searching algorithm that works on a sorted list of elements. It repeatedly divides the search interval in half, comparing the middle element with the target value. If the middle element is equal to the target value, the search is successful. If the target value is less than the middle element, the search continues on the lower half of the list, and if it is greater, the search continues on the upper half of the list. The algorithm continues until the target value is found or the search interval is empty.
How Algorithm Works
The algorithm works by repeatedly dividing the search interval in half, comparing the middle element with the target value. If the middle element is equal to the target value, the search is successful. If the target value is less than the middle element, the search continues on the lower half of the list, and if it is greater, the search continues on the upper half of the list. The algorithm continues until the target value is found or the search interval is empty.
Algorithm Implementation
Here is the implementation of Binary Search in Python:
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 above implementation takes a sorted array and a target value as input and returns the index of the target value in the array using the Binary Search algorithm. The implementation uses two variables, left and right, to define the search interval. Initially, left is set to the beginning of the array and right is set to the end of the array.
The implementation uses a while loop to repeatedly divide the search interval in half. The variable mid is set to the middle index of the search interval. If the middle element is equal to the target value, the search is successful, and the index of the target value is returned. If the target value is less than the middle element, the search continues on the lower half of the search interval by setting right to mid - 1. If the target value is greater than the middle element, the search continues on the upper half of the search interval by setting left to mid + 1. If the target value is not found in the array, the function returns -1.
Time and Space Complexity
The time complexity of Binary Search is O(log n), as each comparison reduces the search interval by half. The space complexity of Binary Search is O(1), as the algorithm uses a constant amount of additional memory regardless of the size of the array.
Example
Let’s run an example using the Binary Search algorithm:
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
print("Index of", target, "in", arr, ":", binary_search(arr, target))
The output of the above code is:
Index of 7 in [1, 3, 5, 7, 9, 11, 13, 15] : 3
The Binary Search algorithm successfully finds the target value 7 in the array at index 3.
Conclusion
Binary Search is a powerful searching algorithm that works on sorted lists of elements. It uses a divide-and-conquer approach to quickly find the target value by repeatedly dividing the search interval in half. The algorithm has a time complexity of O(log n) and a space complexity of O(1), making it an efficient and practical algorithm for many applications.
