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

Search a 2D Matrix

Problem

Given an

m x n

matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row, return true if

target

exists in the matrix.

Input: matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3  →  True
Input: matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=13 →  False

Approach — Binary Search on Flattened Index Space

The matrix rows are contiguous — treat it as a single sorted array of

m*n

elements. Map flat index

mid

→

(row, col)

via:

row = mid // n
col = mid % n

Search space:

[0, m*n-1]

l = 0
→ first element of matrix
r = m*n-1
→ last element of matrix

Mid variant: Lower mid

l + (r-l)//2

Condition true moves
r
down via
r = mid
→ need
mid = l
on 2 elements → lower mid

Shrink logic: Find exact target

matrix[row][col] < target
→ too small, eliminate →
l = mid + 1
matrix[row][col] >= target
→ candidate, keep →
r = mid
matrix[row][col] == target
→ early return inside loop (optimization)

Post-loop: Exact match search →

l

is best candidate, must verify.

Code

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        m, n = len(matrix), len(matrix[0])
        l, r = 0, m * n - 1                 # [0, m*n-1]: flattened index space

        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

            row, col = mid // n, mid % n     # map flat index → 2D coordinates

            if matrix[row][col] == target:   # exact match: early return (optimization)
                return True                  # without this, post-loop check still catches it

            if matrix[row][col] < target:    # mid too small, eliminate
                l = mid + 1                  # [mid+1, r]: mid goes OUT

            else:                            # mid too large, keep as candidate
                r = mid                      # [l, mid]: mid stays IN

        row, col = l // n, l % n            # map final candidate to 2D
        return matrix[row][col] == target    # exact match search: must verify post-loop

Trace

matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], n=4, target=3

l=0, r=11 → mid=5  → row=1,col=1 → 11>3  → r=5
l=0, r=5  → mid=2  → row=0,col=2 → 5>3   → r=2
l=0, r=2  → mid=1  → row=0,col=1 → 3==3  → return True ✓

target=13

l=0,  r=11 → mid=5  → row=1,col=1 → 11<13 → l=6
l=6,  r=11 → mid=8  → row=2,col=0 → 23>13 → r=8
l=6,  r=8  → mid=7  → row=1,col=3 → 20>13 → r=7
l=6,  r=7  → mid=6  → row=1,col=2 → 16>13 → r=6
l=6,  r=6  → exit
row=1,col=2 → 16 != 13 → return False ✓

target=7                                    # last element — post-loop check case

l=0,  r=11 → mid=5  → row=1,col=1 → 11>7  → r=5
l=0,  r=5  → mid=2  → row=0,col=2 → 5<7   → l=3
l=3,  r=5  → mid=4  → row=1,col=0 → 10>7  → r=4
l=3,  r=4  → mid=3  → row=0,col=3 → 7==7  → return True ✓

Complexity


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

Koko Eating Bananas

Problem

Koko can eat at most

k

bananas per hour. Given

piles

of bananas and

h

hours, return the minimum integer

k

such that she can eat all bananas within

h

hours.

Input: piles=[3,6,7,11], h=8  →  Output: 4
Input: piles=[30,11,23,4,20], h=5  →  Output: 30

Approach — Binary Search on Value Space (Minimize)

Search space:

[1, max(piles)]

l = 1
→ minimum possible speed (speed 0 → division by zero)
r = max(piles)
→ maximum needed speed (eats largest pile in exactly 1 hour)

Mid variant: Lower mid

l + (r-l)//2

Condition true moves
r
down via
r = mid
→ need
mid = l
on 2 elements → lower mid

Shrink logic: Find first speed where

can_eat(speed)

is True

can_eat flips F → T as speed increases:
speed:    1     2     3     4     5     6  ...
can_eat:  F     F     F     T     T     T
                            ↑
                      first True = minimum speed

can_eat(mid) == True
→ mid works, but maybe slower works →
r = mid
can_eat(mid) == False
→ mid too slow, eliminate →
l = mid + 1

Post-loop: Condition search →

l

guaranteed to be the first speed where

can_eat

is True.

Why Lower Mid (Minimize = First True)

First True → lower mid + r=mid   (pull right boundary down to first True)
Last True  → upper mid + l=mid   (pull left boundary up to last True)

Minimize problems always find first True → always lower mid.

Feasibility Check

def can_eat(x):
    hours = 0
    for pile in piles:
        hours += math.ceil(pile / x)  # hours to finish this pile at speed x
        if hours > h:                 # early exit: already over budget
            return False
    return True                       # hours <= h guaranteed here

if hours <= h: return True / return False
simplifies to just
return True
since early exit already handles the False case.

Code

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        def can_eat(x):
            hours = 0
            for pile in piles:
                hours += math.ceil(pile / x)  # ceil: partial pile still costs 1 hour
                if hours > h:                 # early exit optimisation
                    return False
            return True                       # within budget

        l, r = 1, max(piles)                 # [1, max]: l=0 causes division by zero

        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 can_eat(mid):                 # speed works, try slower
                r = mid                      # [l, mid]: mid stays IN

            else:                            # too slow, eliminate
                l = mid + 1                  # [mid+1, r]: mid goes OUT

        return l                             # first speed where can_eat is True = minimum

Trace

piles=[3,6,7,11], h=8

l=1,  r=11 → mid=6  → can_eat(6):  1+1+2+2=6  <=8 True  → r=6
l=1,  r=6  → mid=3  → can_eat(3):  1+2+3+4=10 >8  False → l=4
l=4,  r=6  → mid=5  → can_eat(5):  1+2+2+3=8  <=8 True  → r=5
l=4,  r=5  → mid=4  → can_eat(4):  1+2+2+3=8  <=8 True  → r=4
l=4,  r=4  → exit
return 4 ✓

Complexity


Time	`O(n log m)` — binary search over `[1, max(piles)]` × O(n) feasibility check
Space	`O(1)` — no extra space beyond loop variables

Capacity To Ship Packages Within D Days

Problem

Given

weights

of packages in order and

days

to ship, return the minimum ship capacity such that all packages are shipped within

days

days. Packages must be shipped in order.

Input: weights=[1,2,3,4,5,6,7,8,9,10], days=5  →  Output: 15
Input: weights=[3,2,2,4,1,4], days=3            →  Output: 6

Approach — Binary Search on Value Space (Minimize)

Search space:

[max(weights), sum(weights)]

l = max(weights)
→ minimum viable capacity (must fit heaviest single package)
r = sum(weights)
→ maximum needed capacity (ship everything in 1 day)

Mid variant: Lower mid

l + (r-l)//2

Condition true moves
r
down via
r = mid
→ need
mid = l
on 2 elements → lower mid

Shrink logic: Find first capacity where

can_ship(capacity)

is True

can_ship flips F → T as capacity increases:
capacity:  max(w)-1   max(w)   ...   answer   ...   sum(w)
can_ship:     F          ?            T               T
                                      ↑
                               first True = minimum capacity

can_ship(mid) == True
→ mid works, but maybe less capacity works →
r = mid
can_ship(mid) == False
→ mid too small, eliminate →
l = mid + 1

Post-loop: Condition search →

l

(==

r

) guaranteed to be minimum valid capacity.

Why
`l = max(weights)`
not
`max(weights) - 1`

capacity < max(weights) → heaviest package can never be loaded → can never ship
So max(weights) is the true lower bound, not max(weights)-1.
The commented solution uses max(weights)-1 as a sentinel (open boundary trick),
but [max(weights), sum(weights)] with standard template is cleaner.

Feasibility Check

def can_ship(capacity):
    curr = 0       # current day load
    curr_day = 1   # start on day 1
    for weight in weights:
        curr += weight
        if curr > capacity:    # overflow: start a new day
            curr_day += 1
            curr = weight      # current package starts the new day
    return curr_day <= days

Simpler than the commented version — no need for index tracking or inner while loop. Just greedily load each package; overflow triggers a new day.

Code

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:

        def can_ship(capacity):
            curr = 0
            curr_day = 1
            for weight in weights:
                curr += weight
                if curr > capacity:      # can't fit: start new day
                    curr_day += 1
                    curr = weight        # this package starts the new day
            return curr_day <= days      # did we finish within budget?

        l, r = max(weights), sum(weights)  # [max, sum]: both are valid bounds

        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 can_ship(mid):              # capacity works, try smaller
                r = mid                    # [l, mid]: mid stays IN

            else:                          # too small, eliminate
                l = mid + 1               # [mid+1, r]: mid goes OUT

        return l                           # first capacity where can_ship is True = minimum

Trace

weights=[1,2,3,4,5,6,7,8,9,10], days=5

l=10, r=55

mid=32 → can_ship(32): [1..10]=55, days needed=2  True  → r=32
mid=21 → can_ship(21): days needed=3               True  → r=21
mid=15 → can_ship(15): [1-5]=15,[6-9]=?            
         day1: 1+2+3+4+5=15 ✓
         day2: 6+7=13, +8=21>15 → new day
         day3: 8+9=17>15 → new day
         day4: wait... let me recount:
         day1: 1+2+3+4+5=15
         day2: 6+7 → 6+7=13, 13+8=21>15 → day2=6+7=13, new day
         day3: 8+9=17>15 → day3=8, new day
         day4: 9+10=19>15 → day4=9, new day
         day5: 10
         5 days ✓ True → r=15
mid=12 → can_ship(12): days needed > 5  False → l=13
mid=13 → can_ship(13): days needed > 5  False → l=14
mid=14 → can_ship(14): days needed > 5  False → l=15
l=15, r=15 → exit
return 15 ✓

Commented Version vs Clean Version

	Commented	Clean
Bounds	`[max-1, sum+1]` open sentinel trick	`[max, sum]` standard closed
Loop condition	`r > l+1`	`l < r`
Return	`r` (first True)	`l` (same, l==r at exit)
Feasibility	inner while loop + index tracking	single for loop, cleaner

Both are correct — the commented version uses open boundaries as sentinels to avoid checking edge cases, a valid pattern but adds mental overhead.

Complexity


Time	`O(n log W)` — binary search over `[max, sum]` × O(n) feasibility check
Space	`O(1)` — no extra space beyond loop variables

Find Minimum in Rotated Sorted Array

Problem

Given a sorted array rotated at some pivot, find the minimum element. All values are unique.

Input: nums=[3,4,5,1,2]    →  Output: 1
Input: nums=[4,5,6,7,0,1,2]→  Output: 0
Input: nums=[1]             →  Output: 1  (not rotated)
Input: nums=[1,2,3,4,5]    →  Output: 1  (not rotated)

Core Insight

Rotated:  [4, 5, 6, 7, | 1, 2, 3]
                         ↑
                     min = pivot

nums[r] is always in the RIGHT (smaller) portion.
Comparing nums[mid] to nums[r] tells you which side of the pivot mid is on:

  nums[mid] > nums[r]  →  mid is LEFT of pivot  →  min is to the RIGHT
  nums[mid] < nums[r]  →  mid is RIGHT of pivot →  min is here or further LEFT

Approach — Binary Search on Index Space

Search space:

[0, n-1]

l = 0
→ first element
r = n-1
→ last element

Mid variant: Lower mid

l + (r-l)//2

Condition true moves
r
down via
r = mid
→ need
mid = l
on 2 elements → lower mid

Shrink logic: Find first index where element is the minimum

nums[mid] < nums[r]
→ mid is in right portion, min is mid or left →
r = mid
nums[mid] > nums[r]
→ mid is in left portion, min is right of mid →
l = mid + 1

Post-loop: Condition search →

l

guaranteed to be the minimum, no verify needed.

Code

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

        l, r = 0, len(nums) - 1         # [0, n-1]: answer always exists in array

        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 nums[mid] < nums[r]:      # mid in RIGHT portion: min is mid or left
                r = mid                  # [l, mid]: mid stays IN

            else:                        # mid in LEFT portion: min is right of mid
                l = mid + 1             # [mid+1, r]: mid eliminated

        return nums[l]                   # condition search: l==r is the minimum

Trace

nums=[4,5,6,7,0,1,2]

l=0, r=6 → mid=3 → nums[3]=7 > nums[6]=2 → l=4
l=4, r=6 → mid=5 → nums[5]=1 < nums[6]=2 → r=5
l=4, r=5 → mid=4 → nums[4]=0 < nums[5]=1 → r=4
l=4, r=4 → exit
return nums[4]=0 ✓

nums=[1,2,3,4,5]             # not rotated: works identically

l=0, r=4 → mid=2 → nums[2]=3 < nums[4]=5 → r=2
l=0, r=2 → mid=1 → nums[1]=2 < nums[2]=3 → r=1
l=0, r=1 → mid=0 → nums[0]=1 < nums[1]=2 → r=0
l=0, r=0 → exit
return nums[0]=1 ✓

nums=[2,1]                   # 2-element case

l=0, r=1 → mid=0 → nums[0]=2 > nums[1]=1 → l=1
l=1, r=1 → exit
return nums[1]=1 ✓

Why Not Compare to
`nums[l]`
?

nums[l] is always in the LEFT (larger) portion after rotation.
Comparing nums[mid] to nums[l] can't reliably locate the pivot:

  [1, 2, 3, 4, 5] not rotated: nums[l]=1 <= nums[mid]=3 → looks like left portion
  [3, 4, 5, 1, 2]   rotated:   nums[l]=3 <= nums[mid]=5 → same signal, different meaning

nums[r] is always in the RIGHT (smaller) portion — reliable anchor.

With Duplicates (LC 154)

if nums[mid] < nums[r]:
            r = mid
        elif nums[mid] > nums[r]:
            l = mid + 1
        else:                        # nums[mid] == nums[r]: can't determine side
            r -= 1                   # shrink right (compare anchor was r, so shrink r)
                                     # degrades to O(n) worst case

Complexity


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

Search in Rotated Sorted Array

Problem

Given a sorted array rotated at some pivot and a target, return the index of target or -1 if not found. All values are unique.

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

Core Insight

Rotated:  [4, 5, 6, 7, | 1, 2, 3]

At any mid, exactly ONE half is always sorted.
Use the sorted half as a reliable range to decide where target must be:

  → If target is inside the sorted half: eliminate the other half
  → If target is outside the sorted half: eliminate the sorted half

Approach — Binary Search with Sorted Half Detection

Search space:

[0, n-1]

l = 0
→ first element
r = n-1
→ last element

Loop condition:

l <= r

(not

l < r

)

Exact match search with early return → need to check single element case too
l < r
would exit before checking the last candidate

Sorted half detection: Compare

nums[l]

nums[mid]

nums[l] <= nums[mid]
→ LEFT half
[l...mid]
is sorted
nums[l] > nums[mid]
→ RIGHT half
[mid+1...r]
is sorted

Shrink logic per branch:

LEFT sorted [l...mid]:
  nums[l] <= target < nums[mid]  →  target inside  → r = mid - 1
  otherwise                      →  target outside → l = mid + 1

RIGHT sorted [mid+1...r]:
  nums[mid] < target <= nums[r]  →  target inside  → l = mid + 1
  otherwise                      →  target outside → r = mid - 1

Post-loop: Returns -1 — exact match always caught by early return inside loop.

Code

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

        l, r = 0, len(nums) - 1          # [0, n-1]: answer always within array

        while l <= r:                     # l<=r: must check single element (last candidate)
            mid = l + (r - l) // 2

            if nums[mid] == target:       # exact match: early return
                return mid

            if nums[l] <= nums[mid]:      # LEFT half [l...mid] is sorted
                if nums[l] <= target < nums[mid]:   # target in sorted left half
                    r = mid - 1          # eliminate right
                else:                    # target in unsorted right half
                    l = mid + 1          # eliminate left

            else:                        # RIGHT half [mid+1...r] is sorted
                if nums[mid] < target <= nums[r]:   # target in sorted right half
                    l = mid + 1          # eliminate left
                else:                    # target in unsorted left half
                    r = mid - 1          # eliminate right

        return -1                        # target not found

Trace

nums=[4,5,6,7,0,1,2], target=0

l=0, r=6 → mid=3 → nums[3]=7 != 0
  nums[0]=4 <= nums[3]=7 → LEFT sorted [4,5,6,7]
  4 <= 0 < 7? No → l=4

l=4, r=6 → mid=5 → nums[5]=1 != 0
  nums[4]=0 <= nums[5]=1 → LEFT sorted [0,1]
  0 <= 0 < 1? Yes → r=4

l=4, r=4 → mid=4 → nums[4]=0 == 0 → return 4 ✓

nums=[4,5,6,7,0,1,2], target=3

l=0, r=6 → mid=3 → nums[3]=7 != 3
  LEFT sorted [4,5,6,7]: 4<=3<7? No → l=4

l=4, r=6 → mid=5 → nums[5]=1 != 3
  LEFT sorted [0,1]: 0<=3<1? No → l=6

l=6, r=6 → mid=6 → nums[6]=2 != 3
  LEFT sorted [2,2]: 2<=3<2? No → l=7

l=7 > r=6 → exit
return -1 ✓

Why
`l <= r`
and not
`l < r`

l < r  exits at 1 element without checking it → misses the answer
l <= r checks single element via nums[mid]==target → catches it

This is the exact match template:
  l < r  → condition search (answer guaranteed by invariant)
  l <= r → exact match search (must check each candidate, return -1 if none match)

Boundary Conditions — Why Strict Inequalities Matter

if nums[l] <= target < nums[mid]:    # note: <= on left, strict < on right

nums[mid] == target  → caught by early return above, never reaches here
nums[l]   == target  → must be included (<=), it's a valid candidate in left half
nums[r]   == target  → must be included (<=) in right half check

Getting these wrong causes misclassification of target into the wrong half.

Complexity


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

Search in Rotated Sorted Array II — With Duplicates (LC 81)

Problem

Same as LC 33 but array may contain duplicates. Return true/false instead of index.

Input: nums=[2,5,6,0,0,1,2], target=0  →  True
Input: nums=[2,5,6,0,0,1,2], target=3  →  False
Input: nums=[1,0,1,1,1],     target=0  →  True

Why Duplicates Break LC 33

[1, 1, 1, 3, 1],  mid = 2

nums[l]=1 == nums[mid]=1  →  can't tell which half is sorted:
  could be [1,1,1] sorted left + [3,1] unsorted right
  could be [1,1]   unsorted left + [1,1] sorted right... ambiguous

Fix: when nums[l] == nums[mid], just skip l forward by 1.
     Can't determine sorted half, but we know nums[l] != target
     (already checked nums[mid]==target above, and nums[l]==nums[mid])

What Changes from LC 33

Only one extra branch — everything else is identical:

LC 33:  if nums[l] <= nums[mid]:   # sorted half detection
LC 81:  if nums[l] == nums[mid]:   # NEW: can't determine → skip
            l += 1
        elif nums[l] < nums[mid]:  # left sorted (strict now, == handled above)
            ...
        else:                      # right sorted
            ...

Code

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

        l, r = 0, len(nums) - 1          # [0, n-1]: answer always within array

        while l <= r:                     # l<=r: exact match, check every candidate
            mid = l + (r - l) // 2

            if nums[mid] == target:       # exact match: early return
                return True

            if nums[l] == nums[mid]:      # duplicate: can't determine sorted half
                l += 1                    # skip l, shrinks space by 1 → O(n) worst case

            elif nums[l] < nums[mid]:     # LEFT half [l...mid] is sorted
                if nums[l] <= target < nums[mid]:   # target in sorted left half
                    r = mid - 1          # eliminate right
                else:                    # target in unsorted right half
                    l = mid + 1          # eliminate left

            else:                        # RIGHT half [mid+1...r] is sorted
                if nums[mid] < target <= nums[r]:   # target in sorted right half
                    l = mid + 1          # eliminate left
                else:                    # target in unsorted left half
                    r = mid - 1          # eliminate right

        return False                     # target not found

Trace

nums=[1,0,1,1,1], target=0              # tricky duplicate case

l=0, r=4 → mid=2 → nums[2]=1 != 0
  nums[0]=1 == nums[2]=1 → can't tell → l=1

l=1, r=4 → mid=2 → nums[2]=1 != 0
  nums[1]=0 < nums[2]=1 → LEFT sorted [0,1]
  0 <= 0 < 1? Yes → r=1

l=1, r=1 → mid=1 → nums[1]=0 == 0 → return True ✓

nums=[2,5,6,0,0,1,2], target=3

l=0, r=6 → mid=3 → nums[3]=0 != 3
  nums[0]=2 > nums[3]=0 → RIGHT sorted [0,0,1,2]
  0 < 3 <= 2? No → r=2

l=0, r=2 → mid=1 → nums[1]=5 != 3
  nums[0]=2 < nums[1]=5 → LEFT sorted [2,5]
  2 <= 3 < 5? Yes → r=0

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

l=1 > r=0 → exit
return False ✓

LC 33 vs LC 81 Comparison

	LC 33 (no duplicates)	LC 81 (duplicates)
Returns	index or -1	true or false
Sorted half detection	`nums[l] <= nums[mid]`	`nums[l] == nums[mid]` → `l+=1` first
Time complexity	`O(log n)`	`O(n)` worst, `O(log n)` average
Extra branch	none	`nums[l] == nums[mid]: l += 1`

Complexity


Time	`O(n)` worst case (all duplicates), `O(log n)` average
Space	`O(1)` — no extra space, pointers only

Time Based Key-Value Store

Problem

Design a time-based key-value store that can store multiple values for the same key at different timestamps and retrieve the value at a given timestamp.

Implement:

set(key, value, timestamp)
— stores key/value at timestamp (timestamps always increasing)
get(key, timestamp)
— returns value with largest timestamp
<= timestamp
, or
""
if none

set("foo", "bar", 1)
get("foo", 1)   →  "bar"
get("foo", 3)   →  "bar"   (largest timestamp <= 3 is 1)
set("foo", "bar2", 4)
get("foo", 4)   →  "bar2"
get("foo", 5)   →  "bar2"  (largest timestamp <= 5 is 4)

Approach — Binary Search on Timestamp (Find Last True)

Data structure:

defaultdict(list)

mapping

key → [(timestamp, value), ...]

Timestamps are always inserted in increasing order → list is always sorted → binary search valid

Search space:

[0, len(res)-1]

(indices into the list for a given key)

l = 0
→ earliest timestamp for this key
r = len-1
→ latest timestamp for this key

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

res[mid][0] <= timestamp

timestamps: [1, 3, 5, 7, ...], query timestamp = 6
condition:   T  T  T  F  ...
                        ↑
              last True = answer (largest timestamp <= query)

res[mid][0] > timestamp
→ mid too large, eliminate →
r = mid - 1
res[mid][0] <= timestamp
→ mid is a valid candidate, keep →
l = mid

Post-loop: Exact match search —

res[l][0]

could still be

> timestamp

if ALL timestamps are greater than query → verify and return

""

Code

class TimeMap:

    def __init__(self):
        self.hm = defaultdict(list)        # key → [(timestamp, value), ...]

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.hm[key].append((timestamp, value))  # timestamps always increasing → stays sorted

    def get(self, key: str, timestamp: int) -> str:
        res = self.hm[key]

        if len(res) == 0:                  # key never set
            return ""

        l, r = 0, len(res) - 1            # [0, n-1]: search over stored timestamps

        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 res[mid][0] > timestamp:    # mid timestamp too large, eliminate
                r = mid - 1               # [l, mid-1]: mid goes OUT

            else:                          # res[mid][0] <= timestamp: valid candidate
                l = mid                    # [mid, r]: mid stays IN

        if res[l][0] <= timestamp:         # verify: all timestamps could be > query
            return res[l][1]
        return ""                          # no valid timestamp found

Trace

set("foo","bar",1)   → hm["foo"] = [(1,"bar")]
set("foo","bar2",4)  → hm["foo"] = [(1,"bar"),(4,"bar2")]

get("foo", 3):
  res=[(1,"bar"),(4,"bar2")], l=0, r=1

  l=0, r=1 → mid=1 → res[1][0]=4 > 3 → r=0
  l=0, r=0 → exit
  res[0][0]=1 <= 3 → return "bar" ✓

get("foo", 4):
  l=0, r=1 → mid=1 → res[1][0]=4 <= 4 → l=1
  l=1, r=1 → exit
  res[1][0]=4 <= 4 → return "bar2" ✓

get("foo", 0):                             # all timestamps > query
  l=0, r=1 → mid=1 → res[1][0]=4 > 0 → r=0
  l=0, r=0 → exit
  res[0][0]=1 > 0 → return "" ✓

Why Upper Mid (Last True = Maximize)

Last True  → upper mid + l=mid   (pull left boundary up to last True)
First True → lower mid + r=mid   (pull right boundary down to first True)

We want LARGEST timestamp <= query = last True → upper mid.

2 elements: l=0, r=1
  lower mid → mid=0 → res[0][0]<=ts → l=mid=0 → FREEZE
  upper mid → mid=1 → res[1][0]<=ts → l=mid=1 → l==r, exits ✓

Complexity


Time `set`	`O(1)` — append to list
Time `get`	`O(log n)` — binary search over timestamps for given key
Space	`O(n)` — storing all key/value/timestamp triples

Binary Search Master Template

Step 1: Define Search Space

Step 2: Pick Mid Variant

How to remember

Step 3: Shrink Space

Step 4: Post-loop Check

Templates

Template A — Lower Mid

Template B — Upper Mid

Cheatsheet

Search Insert Position

Problem

Approach — Binary Search on Index Space

Code

Trace

Complexity

Guess Number Higher or Lower

Problem

Approach — Binary Search on Value Space

Code

Trace

Why Upper Mid here

Complexity

Sqrt(x)

Problem

Approach — Binary Search on Value Space

Code

Trace

Why Upper Mid here

Complexity

Search a 2D Matrix

Problem

Approach — Binary Search on Flattened Index Space

Code

Trace

Complexity

Koko Eating Bananas

Problem

Approach — Binary Search on Value Space (Minimize)

Why Lower Mid (Minimize = First True)

Feasibility Check

Code

Trace

Complexity

Capacity To Ship Packages Within D Days

Problem

Approach — Binary Search on Value Space (Minimize)

Why l = max(weights) not max(weights) - 1

Feasibility Check

Code

Trace

Commented Version vs Clean Version

Complexity

Find Minimum in Rotated Sorted Array

Problem

Core Insight

Approach — Binary Search on Index Space

Code

Trace

Why Not Compare to nums[l]?

With Duplicates (LC 154)

Complexity

Search in Rotated Sorted Array

Problem

Core Insight

Approach — Binary Search with Sorted Half Detection

Code

Trace

Why l <= r and not l < r

Boundary Conditions — Why Strict Inequalities Matter

Complexity

Search in Rotated Sorted Array II — With Duplicates (LC 81)

Problem

Why Duplicates Break LC 33

What Changes from LC 33

Code

Trace

LC 33 vs LC 81 Comparison

Complexity

Time Based Key-Value Store

Why
`l = max(weights)`
not
`max(weights) - 1`

Why Not Compare to
`nums[l]`
?

Why
`l <= r`
and not
`l < r`