Part 7: Searching Algorithms in Python – Mastering Binary Search and Beyond

🚀 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

✅ 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 
 

💬 Have a binary search trick or a real interview example? Let’s chat in the comments! 🔎🐍