The Half-Life Search

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

A lookup service keeps its record IDs as a sorted list of integers and resolves a query to the slot it occupies. Return the index of target in nums, or -1 when it is absent. The list can be large and the ordering is guaranteed, so the lookup should not have to scan every element.

Every guess cuts the problem in half.

Example 1

Input:

nums = [1,3,5,7,9,11,13], target = 7

Output:

3

Example 2

Input:

nums = [1,3,5,7,9], target = 6

Output:

-1

Worked solution and explanation

What this problem really is

Underneath the lookup-service framing, this is two pointers closing on a target through systematic halving, and the whole problem lives in the boundary conditions. Anyone can sketch the midpoint compare. What separates candidates is the loop termination and the pointer updates: get either one slightly wrong and the function either hangs forever on a two-element range or skips the one slot that holds the answer. The sorted guarantee is the permission slip to throw away half the array every iteration; if you scan linearly you have answered a different, easier question.

Walk through the decisions

Step 1: Bracket the whole array, inclusively

Set low = 0 and high = len(nums) - 1. These bracket the inclusive range still in play. Starting high at len(nums) instead is the off-by-one that reads past the end on the first compare.

Step 2: Halve, and always shrink the range

Compute mid = (low + high) // 2, compare nums[mid] to the target, and move the pointer on the losing side past mid: low = mid + 1 or high = mid - 1. The + 1 / - 1 is what guarantees the range actually shrinks. Assigning low = mid lets a two-element window repeat forever.

Step 3: Terminate on a crossed bracket

Loop while low <= help is wrong on purpose to make you read it: the condition is low <= high. The <= keeps the single-element range alive long enough to check it. Return mid on a hit; fall out of the loop to return -1 when the brackets cross.

The solution

Classic binary search with pointer narrowing
def binary_search(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Common follow-up questions