Binary search — iterative, recursive; O(log n); searching in sorted - rotated arrays: Foundations

This page builds every one of those ideas from nothing, in the order they stack on top of each other. If you already know one, the reveal line at the end lets you skip it.

1. What an array is, and what an index means

Look at the figure: the numbers inside the boxes are the values; the numbers below are the indices. These two rows are different things — mixing them up is the single most common beginner error.

Figure — Binary search — iterative, recursive; O(log n); searching in sorted - rotated arrays

An array of $n$ values has indices running from $0$ up to $n - 1$ . That last index is $n - 1$ , not $n$ — there is no box $n$ . This is why the parent note writes hi = n - 1 at the start.

2. What sorted means — the precondition

Without the staircase, that reasoning collapses — a short middle bar tells you nothing about the left side. That is exactly why the parent lists "the array must be sorted" as a precondition and why running binary search on unsorted data gives garbage.

The symbol $\leq$ ("less than or equal to") appears constantly. Read it as "at most". Its cousin $<$ means "strictly less, not equal". The difference matters: two boxes can hold the same value in a sorted list, so we usually need $\leq$ , not $<$ .

3. What a half is, and why we cut in the middle

The floor bracket $⌊ ⌋$ appears in the mid formula. It means "round down to a whole number", because an index must be a whole box number — there is no box $2.5$ . So $⌊ 2.5 ⌋ = 2$ .

4. Powers of two — the doubling ladder

5. The logarithm — "how many halvings?"

Check it against the ladder: $2^{10} = 1024$ , so $lo g_{2} 1024 = 10$ . That is the parent note's "ten guesses for a number up to 1000" — ten halvings shrink 1024 down to 1. See Logarithms for the full treatment.

6. Big-O, informally — the shape of growth

7. Recurrence relation — describing a self-referring process

8. Reading the code symbols

Prerequisite map

Everything on the left builds the target on the right. Miss one prerequisite and a symbol in the parent note will feel unearned.

Linear Search — the $O (n)$ baseline binary search beats.
Sorting Algorithms — how the precondition (a sorted array) is created.
Logarithms · Recurrence Relations · Time Complexity & Big-O — the growth-analysis toolkit.
Lower & Upper Bound (bisect) — binary search's close relatives for ranges of equal values.
Binary Search Tree — the same halving idea baked into a data structure.
Back to the parent: Hinglish version.

Equipment checklist

In arr = [10, 20, 30], what index holds 30, and what is the last valid index?

Index 2; the last valid index is

n - 1 = 2

What does "sorted ascending" require of every neighbouring pair?

arr [i] \leq arr [i + 1]

— each value at most the next (staircase never steps down).

Compute the middle index of a window with lo = 4, hi = 9.

mid = 4 + ⌊(9 - 4) /2 ⌋ = 4 + 2 = 6

Why cut at the middle rather than anywhere else?

It makes the two halves as equal as possible, minimising the worst-case surviving half → fewest steps.

Evaluate

lo g_{2} 64

and say what it counts.

6

; the number of halvings to shrink 64 down to 1 (equivalently,

2^{6} = 64

What is

7//2

and what LaTeX symbol does // mirror?

3

; it mirrors the floor

⌊ ⌋

(integer division discards the remainder).

What does the recurrence

T (n) = T (n /2) + 1

say in plain words?

The work on

n

items is the work on half of them plus one comparison.

Why is -1 used for "not found"?

It can never be a real index (indices start at 0), so it's an unambiguous "no match" signal.

Recall Two-sentence summary

A sorted array is a staircase; the middle box tells you which half of the staircase your target sits on, so each look throws away half the boxes. The number of throw-away steps is the logarithm base 2 of the array size — which is why the whole thing is $O (lo g n)$ .