🏷️ Category: Algorithms / Search | 🎯 Difficulty: Easy | 🔥 Frequency: ★★★★★
📋 Problem Statement
Given a sorted list and a target, return the index of the target using Binary Search. Return -1 if not found.
📥 Input → nums = [1, 3, 5, 7, 9, 11], target = 7
📤 Output → 3
📥 Input → nums = [1, 3, 5, 7, 9, 11], target = 6
📤 Output → -1
🧠 What the Interviewer is Testing
| Concept | Why It Matters |
|---|---|
| Divide and conquer | Core algorithm pattern |
| Off-by-one errors | Careful pointer handling |
| O(log n) awareness | Efficiency over linear search |
⚠️ Key requirement: Array must be sorted. Always mention this constraint.
💡 Approach
Keep two pointers: low and high
While low <= high:
Find mid = (low + high) // 2
If nums[mid] == target → return mid
If nums[mid] < target → search right half (low = mid + 1)
If nums[mid] > target → search left half (high = mid - 1)
Return -1 if not found
✅ Optimal Solution
def binary_search(nums: list, target: int) -> int:
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1 # target in right half
else:
high = mid - 1 # target in left half
return -1 # not found
# ── Test Cases ─────────────────────────────────
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # ✅ 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # ✅ -1
print(binary_search([1], 1)) # ✅ 0
🔍 Step-by-Step Walkthrough
nums = [1, 3, 5, 7, 9, 11], target = 7:
| Step | low | high | mid | nums[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 5 | 5 < 7 → low = 3 |
| 2 | 3 | 5 | 4 | 9 | 9 > 7 → high = 3 |
| 3 | 3 | 3 | 3 | 7 | ✅ Found! Return 3 |
📊 Complexity Analysis
┌──────────────┬────────────────────────────────────────────┐
│ Time O(logn) │ Search space halves each iteration │
│ Space O(1) │ Only two pointers used, no extra memory │
└──────────────┴────────────────────────────────────────────┘
🎤 How to Explain in the Interview
“Binary search works on sorted arrays by repeatedly halving the search space. I maintain low and high pointers and check the middle element. If it matches I return the index. If the target is larger I move low up, if smaller I move high down. This gives O(log n) compared to linear search’s O(n).”
“Binary search works on sorted arrays by repeatedly halving the search space. I maintain low and high pointers and check the middle element. If it matches I return the index. If the target is larger I move low up, if smaller I move high down. This gives O(log n) compared to linear search’s O(n).”
🔁 Common Follow-up Questions
Q1 → Recursive version?
def binary_search_recursive(nums, target, low=0, high=None):
if high is None:
high = len(nums) - 1
if low > high:
return -1
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binary_search_recursive(nums, target, mid + 1, high)
else:
return binary_search_recursive(nums, target, low, mid - 1)
Q2 → Find first/last occurrence of duplicate?
# For first occurrence, keep searching left even after finding target
# For last occurrence, keep searching right
📁 Set 1 of 4 — Python Interview Prep Series — devprepguide.com