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

3.6.11 · Coding › Sorting & Searching

WHY binary search exists

Socho 1 se 1000 ke beech ek number guess karna ho. 500 guess karo: "higher/lower" ka reply 500 numbers maar deta hai. Das guesses ( $2^{10} = 1024$ ) kaafi hain. Yahi poora trick hai.

HOW — loop ko first principles se derive karna

Hum ek window [lo, hi] maintain karte hain jo guaranteed hai ki target ko contain karegi agar woh exist karta hai. Yeh invariant hai — baaki sab kuch isko protect karne se aata hai.

Start: lo = 0, hi = n-1 (poora array).
Unke beech mid pick karo. Mid kyun? Yeh window ko as evenly as possible split karta hai, toh worst half as small as possible hota hai → worst case mein kam steps.
arr[mid] ko target se compare karo:
- equal → mila, mid return karo.
- arr[mid] < target → target (agar present hai) right mein hai, toh lo = mid + 1. +1 kyun? mid khud abhi rule out ho gaya; isko rakhne se infinite loop ka risk hai.
- arr[mid] > target → usi wajah se hi = mid - 1.
Ruko jab lo > hi (empty window) → not found.

Iterative code

def bsearch(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                 # window non-empty
        mid = lo + (hi - lo) // 2   # overflow-safe
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1            # discard left half incl. mid
        else:
            hi = mid - 1            # discard right half incl. mid
    return -1

lo <= hi kyun, lo < hi nahi? Jab lo == hi ho toh window mein abhi bhi ek element hai jise humne check nahi kiya — isko drop karna single-element matches miss kar deta.

Recursive code

def bsearch_rec(arr, target, lo, hi):
    if lo > hi:                     # base case: empty
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return bsearch_rec(arr, target, mid + 1, hi)   # right
    return bsearch_rec(arr, target, lo, mid - 1)       # left

Same logic; call stack loop ki jagah le leta hai. Recursion depth $O (lo g n)$ hai, isliye memory $O (lo g n)$ hai iterative ke $O (1)$ ke muqable.

WHY it is $O (lo g n)$ — derived

Maano $T (n)$ = $n$ elements ke liye worst case mein comparisons. Har step $O (1)$ kaam karta hai phir half pe recurse karta hai: $T (n) = T (n /2) + 1, T (1) = 1$ Unrolling: $T (n) = 1 + 1 + \dots$ jab tak $n$ shrink hokar $1$ na ho jaaye. Halvings ki count $k$ satisfy karti hai $n / 2^{k} = 1 \Rightarrow 2^{k} = n \Rightarrow k = lo g_{2} n$ . Toh $T (n) = lo g_{2} n + 1 = O (lo g n)$ Space: iterative $O (1)$ , recursive $O (lo g n)$ (stack).

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

Searching in a ROTATED sorted array

Ek sorted array jo pivot pe rotate hui ho, jaise [4,5,6,7,0,1,2]. Yeh globally sorted nahi rahi, lekin mid ke around kam se kam ek half hamesha sorted hoti hai. Hum iska faayda uthate hain.

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:                 # left half sorted
            if arr[lo] <= target < arr[mid]:    # target in left
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                   # right half sorted
            if arr[mid] < target <= arr[hi]:    # target in right
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

arr[lo] <= arr[mid] mein <= kyun? Jab lo == mid ho (window size 1–2) toh "left half" ek single element hai, trivially sorted; <= us case ko sahi rakhta hai. Phir bhi $O (lo g n)$ — har step ek half discard karta hai.

Worked examples

Worked example Plain search —

[1,3,5,7,9,11] mein 7 dhundho

step	lo	hi	mid	arr[mid]	action
1	0	5	2	5	5<7 → lo=3
2	3	5	4	9	9>7 → hi=3
3	3	3	3	7	found! return 3

Step 2 left kyun gaya: mid=4 value 9 overshoot kar gaya, toh target [3,3] mein hona chahiye. 6 elements ke liye teen comparisons ( $⌈ lo g_{2} 6 ⌉ = 3$ ). ✓

Common mistakes (steel-manned)

Recall Feynman: ek 12-saal ke bacche ko samjhao

Tum ek phone book mein ek naam dhundh rahe ho. Tum har naam nahi padhte! Tum beech mein flip karte ho. Jo naam chahiye woh middle se pehle aata hai? Doosra aadha kaat ke ignore karo. Baad mein aata hai? Pehla aadha ignore karo. Jo bacha hai uska middle kholo, repeat karo. Kuch flips mein tum exact page pe pahunch jaate ho. Har flip aadhi book phenkta hai — isliye badi se badi book bhi sirf mutthi bhar flips mein cover ho jaati hai. "Rotated" book woh hai jisme kisi ne pages kaatke swap kar diye; lekin jo piece tum kholte ho woh abhi bhi alphabetical hai, toh tum phir bhi bata sakte ho kaunsa side rakhna hai.

Flashcards

Binary search precondition kya hai?

Array sorted hona chahiye (ya rotated variant ke liye sorted-then-rotated).

Binary search ki time complexity kya hai aur kyun?

O (lo g n)

; recurrence

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

har step pe search half kar deta hai,

lo g_{2} n

steps.

Overflow-safe mid formula kya hai?

mid = lo + (hi - lo) // 2,

(l o + hi) /2

ke barabar lekin integer overflow se bachata hai.

lo = mid + 1 kyun, lo = mid nahi?

mid already compare aur exclude ho chuka hai;

+ 1

ke bina window shrink nahi hogi → infinite loop.

Sahi loop condition kya hai aur kyun?

while lo <= hi; < se tum single remaining element miss kar doge jab lo == hi ho.

Space complexity: iterative vs recursive?

Iterative

O (1)

; recursive

O (lo g n)

call stack depth ki wajah se.

Rotated array mein sorted half kaise dhundhen?

Agar arr[lo] <= arr[mid] toh left half sorted hai; warna right half sorted hai.

Jab sorted half pata chale toh aage kahan jaana hai kaise decide karo?

Range-check: agar target us sorted half ki bounds ke andar hai, wahan search karo; warna doosra half search karo.

Binary search not found hone pe kya return karta hai?

Conventionally

- 1

, tab milta hai jab lo > hi ho (empty window).

Worst case

⌈ lo g_{2} n ⌉

comparisons kyun hote hain?

Har comparison candidate set aadha kar deta hai;

k

halvings ke baad sirf

n / 2^{k}

bachte hain,

k = lo g_{2} n

pe 1 milta hai.

Connections

Linear Search — $O (n)$ baseline; binary search isko tabhi beat karta hai jab data sorted ho.
Sorting Algorithms — pehle sort karna padta hai ( $O (n lo g n)$ ek baar) binary search enable karne ke liye.
Logarithms — halving-ka-inverse jo complexity deta hai.
Recurrence Relations — $T (n) = T (n /2) + 1$ analysis.
Time Complexity & Big-O — $O (lo g n)$ ko $O (1)$ aur $O (n)$ ke beech place karta hai.
Lower & Upper Bound (bisect) — variants jo first/last position dhundhte hain.
Binary Search Tree — same divide idea ek data structure ke roop mein.