AI Hints
Home›DSA in Python Tutorial›Binary Search
DSA in Python · Lesson 46 of 132

Binary Search

Halving a sorted list.

⏱ 2 min read▶ Video at 53:22🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Open a dictionary to find the word mango. You don't start at A. You open somewhere in the middle, see you're at P, and go left. Each look throws away half the book. That's binary search, and it only works because the words are sorted.

Binary Search
From the video: Binary Search
  • Find 'mango' in a dictionary
  • Open the middle, go left or right
  • It needs sorted data

Binary search, step by step

Low and high mark the part of the list that could still hold the target. We look at the middle item. If it's the target, we're done. If it's too small, the target must be to the right, so low moves past the middle. If it's too big, high moves left. We print each step. Run it. Just three looks, to find twenty three among sixteen numbers. For a million numbers, it's never more than about twenty.

binary.pypython
def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        print(f"  look at index {mid}: {nums[mid]}")
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91, 95, 99, 104, 110, 120]
print("found at", binary_search(nums, 23))
Output
  look at index 7: 45
  look at index 3: 12
  look at index 5: 23
found at 5

Binary search rules

The list must be sorted, or binary search gives wrong answers, with no warning. It's O of log N, which is incredibly fast. And it returns minus one, or none, when the target isn't there. The loop condition, low less than or equal to high, is where most bugs hide.

keyvalue
Needssorted data
SpeedO(log n)
Not foundreturn -1
Bug magnetlow <= high, mid ± 1

Summary

Binary search halves a sorted list at every step, so it's O of log N. Next, Python's built in binary search, and tricky edge cases.

Key takeaways
  • Sorted data only
  • Look at the middle
  • Halve each step
Next up: The bisect Module — Python's binary search