Binary Search
Efficient search algorithms on sorted data with O(log n) complexity.
Binary Search
Classic binary search on a sorted array. O(log n) time.
How it works
Binary Search repeatedly divides the search space in half by comparing the middle element. It only works on sorted arrays. Each comparison eliminates half of the remaining elements, resulting in logarithmic time. It's essential for interval/range problems and finding specific values efficiently.
Time Complexity
O(log n)
Space Complexity
O(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