Exercise 1: Binary Search

Your Task

Write a function binary_search(nums, target) that searches for target in a sorted list nums.

Return the index of target if found, or -1 if it is not in the list.

---

Examples

print(binary_search([1, 3, 5, 7, 9], 5))   # 2
print(binary_search([1, 3, 5, 7, 9], 7))   # 3
print(binary_search([1, 3, 5, 7, 9], 4))   # -1
print(binary_search([], 1))                 # -1

---

Expected Complexity

	Complexity
Time	O(log n) — halve the search space each step
Space	O(1) — only two pointers

---

Approach

Keep two pointers, lo and hi, that mark the current search window:

1. Set lo = 0, hi = len(nums) - 1
2. While lo <= hi:
   • Compute mid = (lo + hi) // 2
   • If nums[mid] == target → found, return mid
   • If nums[mid] < target → target is in the right half, set lo = mid + 1
   • If nums[mid] > target → target is in the left half, set hi = mid - 1
3. Loop ended without a match → return -1

---

Starter Code

def binary_search(nums, target):
    pass

print(binary_search([1, 3, 5, 7, 9], 5))   # 2
print(binary_search([1, 3, 5, 7, 9], 7))   # 3
print(binary_search([1, 3, 5, 7, 9], 4))   # -1
print(binary_search([], 1))                 # -1

---

Hints