1 करोड़ sorted numbers में एक number सिर्फ 24 steps में कैसे ढूँढोगे?

1 करोड़ numbers. सिर्फ 24 steps. Let’s make it click.

Dictionary में ‘window’ ढूँढना है. Page 1 से पढ़ना शुरू करोगे? भाई, placement से पहले retirement हो जाएगी. बीच खोलो, W आगे है तो पीछे का आधा छोड़ दो. फिर बचे हुए का बीच. यही Binary Search है.

हर बार आधा — 1 करोड़ से 24 तक

Sorted order हमें एक promise देता है: mid से छोटी values left में, बड़ी right में. Mid target से छोटा है तो left half में target हो ही नहीं सकता. उसे safely discard कर सकते हैं.

1,00,00,000 → 50,00,000 → 25,00,000 → 12,50,000 → … → 1. ceil(log₂(10⁷)) = 24. Standard exact binary search में worst-case करीब 24 comparisons लगते हैं. Linear search में 1 करोड़ तक लग सकते हैं.

remaining ≈ n / 2ᵗ → t ≈ log₂ n

Invariant पकड़ो, template मत रटो

Closed interval [low, high] रख रहे हैं: अगर target मौजूद है, वह इसी interval में है. Loop low <= high तक चलेगा. Mid मिल गया तो return. Target छोटा है तो high = mid - 1; बड़ा है तो low = mid + 1.

हर iteration में interval छोटा होना चाहिए. high = mid या low = mid को गलत template में डालोगे तो infinite loop. Closed और half-open intervals के rules अलग होते हैं — दोनों को mix मत करना.

mid = low + (high - low) / 2

Safe midpoint और sorted की शर्त

(low + high) / 2 में Java/C++ fixed-width int overflow हो सकता है. low + (high - low) / 2 standard nonnegative indices के लिए safe है. Python integers arbitrary precision हैं, पर वही formula पढ़ने में clear रहता है.

Binary Search सिर्फ sorted arrays तक सीमित नहीं: monotonic predicate यानी false,false,true,true जैसी boundary पर भी चलती है. पर unsorted arbitrary data पर आधा हिस्सा बिना proof फेंकना गलत है. एक search के लिए पहले sort करने की cost O(n log n) भी count करना.

Rotated array में भी आधा sorted मिलता है

LC 33 में rotation के बावजूद हर step में एक half sorted होगा. पहले check करो कौन सा half sorted है; फिर देखो target उस range में आता है या नहीं. Distinct values होने पर O(log n). Duplicates वाले variant में ambiguity से O(n) तक degradation हो सकती है.

LC 153 में mid को right endpoint से compare करो. nums[mid] > nums[right] है तो minimum right में है. वरना mid भी minimum हो सकता है, इसलिए right = mid. यह exact-search template से अलग boundary search है.

INTERVIEW में बोलो · तुम्हारा ANSWER

“Sorted data में midpoint compare करके हर step में आधा search space eliminate करूँगा. Invariant है कि target अगर मौजूद है तो [low, high] में है. Search space n / 2ᵗ हो जाता है, इसलिए O(log n) time और iterative version O(1) space. 10⁷ elements के लिए लगभग 24 steps.”

Read it once. फिर अपने words में बोल के देखो.

SPOT IT BEFORE YOU CODE IT

Pattern पहचानो.

Problem में ये दिखे	तब ये use करो	यहाँ नहीं
Sorted, find target	Exact binary search	Unsorted data without a monotonic condition
First true / minimum feasible	Binary search on answer	Predicate true/false बार-बार पलटता हो
Rotated sorted, distinct values	Identify the sorted half	Assuming O(log n) with arbitrary duplicates

SAME LOGIC. YOUR LANGUAGE.

अब code लिखते हैं.

Binary Search · LC 704

Closed interval [low, high]. O(log n) time, O(1) space.

def search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

assert search([3, 7, 11, 15, 19, 23, 27, 31, 35], 27) == 6