Binary Search

Medium

Halve the range every step

Problem

Given a sorted array and a target, return the index of the target using binary search, or -1 if not found.

In simple words

Peek at the middle; if too big look left, too small look right — halving the search each time.

The idea

Compare the target with the middle element and throw away the half it cannot be in. Each step halves the search space, so a sorted array of a million elements is settled in about twenty comparisons.

The trick

Compute mid as `lo + (hi - lo) / 2` to avoid overflow on large bounds.
Keep the loop invariant explicit: the answer, if it exists, is always inside [lo, hi].
O(log n) — the whole reason to keep an array sorted.

←→stepspaceplay

-1

target9

1/6

Brute force

timeO(n)spaceO(1)

Scan one by one.

1// walk the whole array2for (let i = 0; i < n; i++)3  if (nums[i] === target) return i;4return -1;

Input

array: [-1, 0, 3, 5, 9, 12]

Memory

i: —
target: 9
checked: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output:: 4
Explanation:: 9 sits at index 4.

Example 2

Input:: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output:: -1
Explanation:: 2 is absent → -1.

Example 3

Input:: nums = [5], target = 5
Output:: 0
Explanation:: Found at the only index, 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.