Binary Search is one of the most important algorithms in computer science. It finds an element in a sorted array in O(log n) time! 🔍
💡 Think of it like this: You're playing a number guessing game. The number is between 1-100. Instead of guessing 1, 2, 3... you guess 50! "Too high" → try 25. "Too low" → try 37. Each guess eliminates HALF the remaining numbers!
💭 Now it's your turn! Using the approach above, implement your solution in the editor. You've got this! 💪
Step-by-step trace for arr=[1,3,5,7,9,11], target=7:
Why O(log n)? We cut the search space in half each time. For 1,000,000 elements, we need at most ~20 comparisons (log₂ 1,000,000 ≈ 20). Compare to O(n) linear search needing up to 1,000,000 comparisons!
When to use binary search:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # Found it!
elif arr[mid] < target:
left = mid + 1 # Target is in right half
else:
right = mid - 1 # Target is in left half
return -1 # Not found
binary_search([-1,0,3,5,9,12], 9)
4
binary_search([-1,0,3,5,9,12], 2)
-1