🚀 Introduction
Searching is one of the most common operations in programming, and binary search is the crown jewel — fast, efficient, and widely applicable.
In this post, we’ll explore:
✅ Linear Search vs Binary Search
✅ Binary search templates in Python
✅ Real-world problems using binary search
✅ Lower/Upper bound techniques
✅ Searching in rotated arrays and 2D matrices
🔎 1️⃣ Linear Search – Simple but Slow**
def linear_search(arr, target):
for i, num in enumerate(arr):
if num == target:
return i
return -1📦 Time Complexity: O(n)
✅ Best for small or unsorted arrays
❌ Not efficient for large datasets
⚡ 2️⃣ Binary Search – Fast and Precise
Works on sorted arrays by dividing the search space in half at each step.
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📦 Time Complexity: O(log n)
✅ Must be sorted
✅ Used in both 1D and 2D problems
🔁 3️⃣ Binary Search Template (Lower Bound Style)
This version is more flexible and forms the base of many variations.
def lower_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left✅ Finds the first position where target can be inserted.
🧪 4️⃣ Real Problems Using Binary Search
🔹 Search Insert Position
def search_insert(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left🔹 Find First and Last Position of an Element
def find_first_last(nums, target):
def find_bound(is_left):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] > target or (is_left and nums[mid] == target):
right = mid
else:
left = mid + 1
return left
left = find_bound(True)
right = find_bound(False) - 1
if left <= right and right < len(nums) and nums[left] == target and nums[right] == target:
return [left, right]
return [-1, -1]🔹 Search in Rotated Sorted Array
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1🔹 Binary Search in 2D Matrix
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
val = matrix[mid // n][mid % n]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False🎯 5️⃣ Advanced Use Cases
🔸 Minimize the Maximum (Binary Search on Answer)
Use binary search on the value space, not index. Example:
- Minimum capacity to ship packages in D days
Min max distance to place routers
Minimize largest subarray sum
📊 6️⃣ Comparison Summary
| Method | Time | Use Case |
|---|---|---|
| Linear Search | O(n) | Unsorted or small datasets |
| Binary Search | O(log n) | Sorted 1D arrays |
| 2D Binary Search | O(log m*n) | Sorted matrices |
| Binary on Answer | Varies | Optimization problems |
✅ Best Practices
✔️ Always check if the array is sorted before applying binary search
✔️ Use while left < right or while left <= right as per problem
✔️ Avoid infinite loops: always update left/right
✔️ Try implementing both upper and lower bound logic
✔️ For rotated arrays – think in terms of sorted halves
🧠 Summary
✔️ Binary search is the go-to method for efficient searching in sorted data
✔️ Understand different templates for flexible use
✔️ Learn to use it in 1D, 2D, and even on value space
✔️ A must-have technique for interviews and system optimization
🔜 Coming Up Next:
👉 Part 8: Trees and Binary Trees – Traversals, Depth, and Recursive Patterns
We’ll cover:
1. DFS & BFS
Inorder, Preorder, Postorder
Balanced trees, height, diameter
Binary Search Tree (BST) basics