Binary search is a classic algorithm in computer science known for its efficiency in searching sorted arrays. This article aims to shed light on the time complexity of binary search, explaining why it’s considered efficient and providing program code examples to illustrate its working mechanism.
What is Binary Search?
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until narrowing down the possible locations to just one.
Key Features of Binary Search
- Divide and Conquer: Binary search splits the data set in half with each iteration.
- Sorted Data: It requires the data to be sorted beforehand.
- Efficiency: Offers a significant efficiency advantage over linear search methods.
Understanding Time Complexity in Algorithms
Time complexity in algorithms is a measure of the amount of time an algorithm takes to complete as a function of the length of the input.
Time Complexity of Binary Search
- Best-case: O(1), when the central index would directly match the desired value.
- Average and Worst-case: O(log n), where n is the number of elements in the array. This logarithmic time complexity is due to the algorithm dividing the search interval in half with each step.
Program Code Example: Binary Search in Python
Let’s illustrate binary search with a Python example:
Python Code for Binary Search
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return None
# Example usage
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5)) # Outputs: 2 (index of 5 in the array)
Explanation of the Code
- The function
binary_searchtakes a sorted arrayarrand atargetvalue to find. - It uses two pointers,
lowandhigh, to keep track of the search boundaries. - In each iteration, it calculates the middle index (
mid) and compares the value atmidwith thetarget. - Depending on the comparison, it either returns the index (
mid) or adjusts the search boundaries (lowandhigh).
Conclusion
The binary search algorithm’s time complexity of O(log n) makes it a highly efficient method for searching in sorted arrays. The key to its efficiency lies in its divide-and-conquer approach, which significantly reduces the number of comparisons needed to find the target value. The provided code example offers a practical understanding of how binary search operates and why its time complexity is logarithmic.
by the Bito team. 
