🎓 A1Learner
🔍
0 of 47 lessons completed

Binary Search Beyond Sorted Lists

Binary search is a way to find a value by halving a sorted range again and again. Each step drops the half that cannot hold the value.

Spot the signal

A list is sorted in two pieces after a rotation. Each piece is sorted, so halving still has a guide.

nums = [4, 5, 6, 7, 0, 1, 2]
print(nums[:4])
print(nums[4:])

The template

Compare the middle value and move one bound. The loop ends when the bounds cross.

def search(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
print(search([2, 5, 8, 12, 16, 23, 38], 23))
print(search([2, 5, 8, 12, 16, 23, 38], 7))

Worked problem: rotated list

One half of a rotated list is always sorted. The sorted half tells which side to keep.

def search_rotated(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        elif nums[mid] < target <= nums[high]:
            low = mid + 1
        else:
            high = mid - 1
    return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))

Example

def find_minimum(nums):
    low = 0
    high = len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] > nums[high]:
            low = mid + 1
        else:
            high = mid
    return nums[low]
print(find_minimum([4, 5, 6, 7, 0, 1, 2]))

Key points

  • Sorted: arranged in rising order, so a middle value splits the range in two.
  • Use binary search when a sorted list must be searched with few steps.
  • Compare the middle value, then keep only the half that can hold the target.
  • Move the low bound up or the high bound down after each comparison.
  • The range halves each step, so a long list needs only a few steps.
  • Binary search is halving with order as the guide.

The code compares the middle value with the last value. A middle above the last value means the smallest value sits to the right. The bounds close in on the smallest value.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why does binary search need sorted data?