Binary Search

⏱ Time: O(log n)💾 Space: O(1)

Repeatedly divide the search space in half. Compare the middle element with the target — if smaller, search the right half; if larger, search the left half. Requires sorted data.

🎯 When to Use

  • ✓Searching in sorted arrays
  • ✓Finding boundaries (first/last occurrence)
  • ✓Optimization problems (minimize/maximize)
  • ✓Search space can be halved each step

📝 Pseudocode

Binary Search TemplateO(log n)
1function binarySearch(arr, target):
2  left = 0
3  right = arr.length - 1
4
5  while left <= right:
6    mid = left + (right - left) / 2
7    if arr[mid] == target:
8      return mid
9    else if arr[mid] < target:
10      left = mid + 1
11    else:
12      right = mid - 1
13
14  return NOT_FOUND

🏢 Real-World Use Cases

Google
Search indexing

Binary search on sorted inverted index lists to quickly find documents containing a search term.

Amazon
Price range filtering

Finding products within a price range using binary search on a sorted price index.

💡 Practice Problems (5)

1.Binary SearchEasy
→
2.Search in Rotated Sorted ArrayMedium
→
3.Find Minimum in Rotated Sorted ArrayMedium
→
4.Koko Eating BananasMedium
→
5.Find Peak ElementMedium
→
← Back to Patterns