Binary Search

EASY✓ CHIP-TIMEDLC #704 — FULL STATEMENT ↗

The drill: Locate a target value inside a sorted array of distinct integers and report its index — or flag its absence with -1. The array's sorted order is the only lever available; scanning ignores it, searching exploits it.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A sorted array of distinct integers arrives along with a target value, and the drill is to report the index where that target lives.

Sorted and distinct means every value appears at most once and the array never needs re-checking for duplicates — each value maps to exactly one position.

When the target isn't present anywhere in the array, the answer is -1 instead of any real index.

EX 01

nums = [-9, -4, 0, 3, 8, 12, 19] · target = 3

→ 3

MIDDLE-ISH HIT

EX 02

nums = [-9, -4, 0, 3, 8, 12, 19] · target = -9

→ 0

LEFT BOUNDARY

EX 03

nums = [-9, -4, 0, 3, 8, 12, 19] · target = 19

→ 6

RIGHT BOUNDARY

array length can reach into the tens of thousands
values are distinct and arranged in ascending order
target may or may not appear in the array
absence is signaled by returning -1

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A linear scan works but throws away the one fact this array gives you for free: it's sorted. What does sorted order let you rule out with a single comparison?

HINT 2 THE STRUCTURE

Compare the target to the middle element. If they don't match, an entire half of the array can never contain the answer — discard it outright.

HINT 3 ONE STEP FROM THE ANSWER

Keep shrinking a [lo, hi] window: check mid, move lo past it if target is bigger, move hi before it if target is smaller, stop when they cross or you land on a hit.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE HALVING HUNTPATTERN · BINARY SEARCHnums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] · target = 17

STEP 1

Target 17. The window starts as the whole array, indices 0 through 9 — sorted order lets us skip half each step.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/binary-search.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 12 LN

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i, v in enumerate(nums):
            if v == target:
                return i
        return -1

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 6 LN

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }
}

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 16 LN

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 10 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED