Binary Search Master Template

Step 1: Define Search Space

l = smallest possible answer
r = largest possible answer

Space	Use when
`[0, n-1]`	answer is always a valid index
`[0, n]`	answer could be n (e.g. insert at end)
`[1, n]`	1-indexed problems
`[lo, hi]`	value space (speeds, capacities, counts)

Note:
r
can be out of bounds as an index — it's a boundary sentinel.
mid
never reaches
r
since
mid < r
always. Guard with
(mid < n and nums[mid])
if needed.

Step 2: Pick Mid Variant

Lower mid = l + (r-l)//2      → when 2 elements, mid = LEFT  (l)
Upper mid = l + (r-l+1)//2    → when 2 elements, mid = RIGHT (r)

How to remember

Which pointer moves toward
mid
when condition is true?
mid
must equal that pointer on 2 elements — pick the variant that guarantees it.

r = mid  (condition true)  →  mid must equal l  →  LOWER mid  (no +1)
  2 elements: l=0, r=1  →  mid must be 0  →  no +1 added

l = mid  (condition true)  →  mid must equal r  →  UPPER mid  (+1)
  2 elements: l=0, r=1  →  mid must be 1  →  +1 added

mid

doesn't equal the moving pointer on 2 elements → space freezes → infinite loop.

Step 3: Shrink Space

Every branch must strictly shrink the space. Safe pairs:

Mid variant	mid stays IN	mid goes OUT
Lower mid	`r = mid`	`l = mid + 1`
Upper mid	`l = mid`	`r = mid - 1`

Mixing pairs across variants → infinite loop on 2-element space.

Step 4: Post-loop Check

The loop exits when

l == r

(1 candidate remains).

Exact match search  →  verify:    return l if nums[l] == target else -1
Condition search    →  guaranteed: return l directly

In condition search the loop invariant ensures the survivor satisfies the condition — no check needed.

Templates

Template A — Lower Mid

(finding minimum / left boundary / first true)

def binary_search_lower_mid(nums, target):
    l, r = 0, len(nums)              # r = n if insert-at-end is a valid answer

    while l < r:                     # exits when l == r (1 candidate remains)
        mid = l + (r - l) // 2      # lower mid: biases left, mid == l on 2 elements

        if CONDITION(mid):           # condition pulls RIGHT boundary down
            r = mid                  # [l, mid]   — mid stays in
        else:
            l = mid + 1              # [mid+1, r] — mid eliminated

    return l                         # or: return l if nums[l] == target else -1

Template B — Upper Mid

(finding maximum / right boundary / last true)

def binary_search_upper_mid(nums, target):
    l, r = 0, len(nums) - 1         # r = n-1 when answer is always in array

    while l < r:                     # exits when l == r (1 candidate remains)
        mid = l + (r - l + 1) // 2  # upper mid: biases right, mid == r on 2 elements

        if CONDITION(mid):           # condition pulls LEFT boundary up
            l = mid                  # [mid, r]   — mid stays in
        else:
            r = mid - 1              # [l, mid-1] — mid eliminated

    return l                         # or: return l if nums[l] == target else -1

Cheatsheet

Condition true moves	`mid` must equal	Mid variant
`r = mid`	`l` (lower)	`l + (r-l)//2`
`l = mid`	`r` (upper)	`l + (r-l+1)//2`

Goal	Mid variant	Shrink pair	`r` init
Find exact match	lower	`r=mid` / `l=mid+1`	`n-1`
Find first true (≥, ≤)	lower	`r=mid` / `l=mid+1`	`n-1`
Find last true	upper	`l=mid` / `r=mid-1`	`n-1`
Insert position	lower	`r=mid` / `l=mid+1`	`n`
Minimize answer	lower	`r=mid` / `l=mid+1`	`max possible`
Maximize answer	upper	`l=mid` / `r=mid-1`	`max possible`

Search Insert Position

Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be inserted in order.

Input:  nums = [1, 3, 5, 6], target = 5  →  Output: 2
Input:  nums = [1, 3, 5, 6], target = 2  →  Output: 1
Input:  nums = [1, 3, 5, 6], target = 7  →  Output: 4

Approach — Binary Search on Index Space

Search space:

[0, n]

l = 0
→ smallest possible insert position
r = n
→ largest possible insert position (insert at end)

Mid variant: Lower mid

l + (r-l)//2

Condition true moves
l
up → wait, condition moves
r
down → need
mid = l
on 2 elements → lower mid

Shrink logic: Find first index where

nums[i] >= target

nums[mid] < target
→ mid too small, eliminate →
l = mid + 1
nums[mid] >= target
(includes
==
) → mid is a candidate →
r = mid

Post-loop: Condition search →

l

guaranteed to be the answer, no verify needed.

Code

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:

        l, r = 0, len(nums)              # [0, n]: n is valid (insert at end)

        while l < r:                     # exits when l==r, 1 candidate remains
            mid = l + (r - l) // 2      # lower mid: r=mid needs mid==l on 2 elems

            if mid < len(nums) and nums[mid] < target:  # guard: mid never reaches n
                l = mid + 1             # [mid+1, r]: mid eliminated, too small
            else:
                r = mid                 # [l, mid]: mid stays in, could be answer
                                        # handles: nums[mid]==target, nums[mid]>target
                                        # handles: mid==n (out of bounds case via guard)

        return l                        # first index where nums[i] >= target
                                        # == insert position (or found position)

Trace

nums = [1, 3, 5, 6], target = 7        # insert at end case

l=0, r=4
  mid=2 → nums[2]=5 < 7  → l = 3

l=3, r=4
  mid=3 → nums[3]=6 < 7  → l = 4

l=4, r=4 → exit
return 4 ✓

nums = [1, 3, 5, 6], target = 5        # exact match case

l=0, r=4
  mid=2 → nums[2]=5 == 5 → r = 2

l=0, r=2
  mid=1 → nums[1]=3 < 5  → l = 2

l=2, r=2 → exit
return 2 ✓

Complexity


Time	`O(log n)` — search space halves each iteration
Space	`O(1)` — no extra space, pointers only

Guess Number Higher or Lower

Problem

A number is picked from

[1, n]

. You call

guess(num)

which returns:

-1
if your guess is too high
1
if your guess is too low
0
if correct

Find the picked number.

Input: n=10, pick=6  →  Output: 6
Input: n=1,  pick=1  →  Output: 1

Approach — Binary Search on Value Space

Search space:

[1, n]

l = 1
→ smallest possible picked number
r = n
→ largest possible picked number

Mid variant: Upper mid

l + (r-l+1)//2

Condition true moves
l
up via
l = mid
→ need
mid = r
on 2 elements → upper mid

Shrink logic: Find the exact picked number

guess(mid) == -1
→ mid too high → eliminate →
r = mid - 1
guess(mid) == 1
→ mid too low → mid is a candidate floor →
l = mid
guess(mid) == 0
→ exact match → early return (optimization)

Post-loop: Early return handles exact match.

l

at exit is guaranteed to be the answer.

Code

class Solution:
    def guessNumber(self, n: int) -> int:

        l, r = 1, n                          # [1, n]: value space, both inclusive

        while l < r:                         # exits when l==r, 1 candidate remains
            mid = l + (r - l + 1) // 2      # upper mid: l=mid needs mid==r on 2 elems

            if guess(mid) == 0:              # exact match: early return (optimization)
                return mid                   # without this, l=mid still converges correctly

            if guess(mid) == -1:             # mid too high, eliminate
                r = mid - 1                  # [l, mid-1]: mid goes OUT

            else:                            # guess(mid)==1: mid too low, keep as floor
                l = mid                      # [mid, r]: mid stays IN, safe: mid==r on 2 elems

        return l                             # l==r, only candidate remaining

Trace

n=10, pick=6

l=1, r=10
  mid=6  → guess(6)==0  → return 6 ✓

n=10, pick=4             # no early return case

l=1,  r=10 → mid=6  → guess(6)==-1  → r=5
l=1,  r=5  → mid=3  → guess(3)==1   → l=3
l=3,  r=5  → mid=4  → guess(4)==0   → return 4 ✓

n=10, pick=10            # upper bound case

l=1,  r=10 → mid=6  → guess(6)==1   → l=6
l=6,  r=10 → mid=8  → guess(8)==1   → l=8
l=8,  r=10 → mid=9  → guess(9)==1   → l=9
l=9,  r=10 → mid=10 → guess(10)==0  → return 10 ✓

Why Upper Mid here

2 elements: l=4, r=5
  lower mid → mid=4 → guess(4)==1 → l=mid=4 → FREEZE (infinite loop)
  upper mid → mid=5 → guess(5)==1 → l=mid=5 → l==r, exits ✓

l = mid

requires upper mid — if mid doesn't reach

r

on 2 elements, space never shrinks.

Complexity


Time	`O(log n)` — search space halves each iteration
Space	`O(1)` — no extra space, pointers only

Sqrt(x)

Problem

Given a non-negative integer

x

, return the square root of

x

rounded down to the nearest integer. Do not use built-in exponent functions or operators.

Input: x=4   →  Output: 2
Input: x=8   →  Output: 2  (sqrt(8)=2.82..., floor=2)
Input: x=0   →  Output: 0

Approach — Binary Search on Value Space

Search space:

[0, x]

l = 0
→ smallest possible floor sqrt
r = x
→ largest possible floor sqrt (e.g. sqrt(1)=1, sqrt(0)=0)

Mid variant: Upper mid

l + (r-l+1)//2

Condition true moves
l
up via
l = mid
→ need
mid = r
on 2 elements → upper mid

Shrink logic: Find last index where

mid * mid <= x

mid * mid > x
→ mid too large, eliminate →
r = mid - 1
mid * mid <= x
→ mid is a valid floor candidate →
l = mid
mid * mid == x
→ exact match, early return (optimization)

Post-loop: Condition search →

l

is the last position where

mid * mid <= x

→ floor sqrt.

Code

class Solution:
    def mySqrt(self, x: int) -> int:

        l, r = 0, x                          # [0, x]: value space, both inclusive

        while l < r:                         # exits when l==r, 1 candidate remains
            mid = l + (r - l + 1) // 2      # upper mid: l=mid needs mid==r on 2 elems

            curr = mid * mid                 # avoid repeated computation

            if curr == x:                    # exact match: early return (optimization)
                return mid                   # without this, l=mid still converges correctly

            if curr > x:                     # mid too large, eliminate
                r = mid - 1                  # [l, mid-1]: mid goes OUT

            else:                            # curr < x: mid is valid floor, keep
                l = mid                      # [mid, r]: mid stays IN, safe: mid==r on 2 elems

        return l                             # last position where mid*mid <= x = floor sqrt

Trace

x=8

l=0, r=8 → mid=4 → 16>8  → r=3
l=0, r=3 → mid=2 → 4<=8  → l=2
l=2, r=3 → mid=3 → 9>8   → r=2
l=2, r=2 → exit
return 2 ✓  (floor of 2.82...)

x=4

l=0, r=4 → mid=2 → 4==4  → return 2 ✓

x=1

l=0, r=1 → mid=1 → 1==1  → return 1 ✓

x=0

l=0, r=0 → exit immediately
return 0 ✓

Why Upper Mid here

2 elements: l=2, r=3  (searching sqrt of 8)
  lower mid → mid=2 → 4<=8 → l=mid=2 → FREEZE (infinite loop)
  upper mid → mid=3 → 9>8  → r=mid-1=2 → l==r, exits ✓

l = mid

requires upper mid — same reason as Guess Number. Anytime you see

l = mid

in the shrink logic, upper mid is mandatory.

Complexity


Time	`O(log x)` — search space `[0, x]` halves each iteration
Space	`O(1)` — no extra space, pointers only