Binary Search

Binary search क्या है

Binary search sorted array में value ढूँढने का तेज़ तरीका है। हर item जाँचने के बजाय, यह बीच देखता है, फिर वो आधा फेंक देता है जिसमें target नहीं हो सकता। यह आधा करना दोहराने से item बहुत कम steps में मिल जाता है।

आधा करने का विचार

{1, 3, 5, 7, 9, 11} में 7 ढूँढने को: बीच देखिए (5)। चूँकि 7 > 5, जवाब दाएँ आधे में होगा, तो हम बायाँ अनदेखा करते हैं। हम छोटी range पर दोहराते हैं जब तक 7 पर न पहुँचें। हर step काम आधा कर देता है।

Java program

public class BinarySearch {
    public static void main(String[] args) {
        int[] a = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int low = 0, high = a.length - 1, pos = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == target) { pos = mid; break; }
            else if (a[mid] < target) low = mid + 1;   // right jao
            else high = mid - 1;                       // left jao
        }
        System.out.println(pos == -1 ? "Not found" : "Found at " + pos);
    }
}

हम low और high range रखते हैं और बीच जाँचते हैं। बीच छोटा हो तो low दाएँ, बड़ा हो तो high बाएँ ले जाते हैं। मिलने या range खाली होने पर रुकते हैं।

Dry run

Sorted क्यों ज़रूरी है

Binary search target की बीच की value से तुलना करके तय करता है कौन-सा आधा रखना है। वो तभी चलता है जब बीच के बाएँ सब छोटा और दाएँ सब बड़ा हो — यानी array sorted हो। unsorted array पर, एक आधा हटाना ठीक वही item हटा सकता है जिसे आप ढूँढ रहे हैं, गलत परिणाम देकर।

Time complexity

• Binary search: O(log n) — हर step range आधी (sorted data चाहिए)।
• Linear search: O(n) — हर item जाँचता है (किसी भी array पर)।
• Space: O(1) — बस कुछ variables।

दस लाख sorted items को, binary search लगभग 20 steps चाहिए बनाम linear search को दस लाख तक।

आम गलतियाँ

• Unsorted array पर इस्तेमाल करना। पहले sort कीजिए, वरना result गलत।
• गलत mid formula। Overflow बचाने को low + (high - low) / 2 इस्तेमाल कीजिए।
• low/high पर off-by-one। mid + 1 या mid - 1 पर जाइए, mid पर नहीं।
• गलत loop condition। low <= high इस्तेमाल कीजिए, वरना आख़िरी element चूक जाते हैं।

सारांश

• Binary search sorted array में range आधी करके value ढूँढता है।
• बीच जाँचिए, फिर वो आधा रखिए जिसमें target हो सकता है।
• चलने को array sorted होना चाहिए।
• Overflow बचाने को mid = low + (high - low) / 2 इस्तेमाल कीजिए।
• यह O(log n) है — बड़े sorted data पर linear search से बहुत तेज़।

आगे, पहले data sort कीजिए bubble sort से, या दोहराइए Java arrays।