There are no items in your cart
Add More
Add More
| Item Details | Price | ||
|---|---|---|---|
Binary Search is an efficient algorithm for finding an item from a sorted list of elements. It repeatedly divides the search space in half. This explanation covers the iterative and recursive methods, edge cases, and performance considerations.
By using Binary Search, we achieve a time complexity of O(log n), which is much better than the O(n) time complexity of linear search.
Written by: Nerchuko
Sun Jan 5, 2025
For a more detailed explanation of Binary Search, watch this video where I walk you through the concept and implementation in-depth:
In the iterative approach, we use a loop to iteratively reduce the search space by adjusting the `low` and `high` pointers. This is memory efficient because no additional space is used for function calls.
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid # Target found
elif arr[mid] > x:
high = mid - 1 # Search in left half
else:
low = mid + 1 # Search in right half
return -1 # Target not found
The recursive approach divides the search space into smaller subarrays through function calls. It offers a clean implementation but incurs additional space complexity due to recursive call stack.
def binary_search_recursive(arr, x, low, high):
if low > high:
return -1 # Base case: element not found
mid = (low + high) // 2
if arr[mid] == x:
return mid # Target found
elif arr[mid] > x:
return binary_search_recursive(arr, x, low, mid - 1) # Search in left half
else:
return binary_search_recursive(arr, x, mid + 1, high) # Search in right half
Both iterative and recursive methods for Binary Search have the same time complexity of O(log n), but differ in space complexity:
In most scenarios, the iterative method is preferred due to lower space complexity. However, the recursive approach can provide cleaner and more concise code.
Binary Search needs to handle edge cases efficiently to avoid errors. Below are a few edge cases you should be aware of:
If the array is empty, the search should return -1 immediately, as there are no elements to search.
If the array has only one element, the target is either found or not. This case should return the correct index or -1.
The target may be at the beginning (arr[0]) or the end (arr[len(arr)-1]) of the array. The algorithm must correctly identify and return the index in these cases.
If the target is not present in the array, the algorithm should return -1 after exhausting the search space.
For the array [3, 4, 5, 7, 8, 9, 10, 12, 15, 19, 20, 21, 22, 24, 25], when the target is 22, both methods (iterative and recursive) return the index 10.
arr = [3, 4, 5, 7, 8, 9, 10, 12, 15, 19, 20, 21, 22, 24, 25]
target = 22
print(binary_search(arr, target)) # Iterative Method Output: 10
print(binary_search_recursive(arr, target, 0, len(arr) - 1)) # Recursive Method Output: 10
Launch your Graphy