Binary Search

Problem

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Examples

The brute-force approach

Scan the array from left to right. Return the index when you find the target, or -1 if you reach the end without a match.

for i in 0 .. len(nums) - 1:
    if nums[i] == target:
        return i       # found it

return -1              # scanned everything, not here

In the worst case you check every element. O(n). For an array of a million sorted numbers, that's up to a million comparisons. Binary search can do it in about 20.

Spotting the pattern

This is a Binary Search problem. The key question to ask yourself:

Can I eliminate half the remaining search space with each comparison?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.