Binary Search

Binary search क्या है?

मान लीजिए आप dictionary में कोई शब्द ढूँढते हैं। आप शुरू से हर पन्ना नहीं पढ़ते — आप बीच के पास खोलते हैं, देखते हैं कि आपका शब्द पहले है या बाद में, और छलाँग लगाते हैं। Binary search किसी sorted array पर ठीक यही करता है, और यह हर element एक-एक करके जाँचने से नाटकीय रूप से तेज़ है।

एक नियम: array पहले sorted होना चाहिए। यही binary search को हर कदम आधा data सुरक्षित रूप से हटाने देता है।

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

तीन markers रखें: low, high, और उनके बीच mid। Target की बीच वाले से तुलना करें:

• अगर बराबर mid — मिल गया।
• अगर छोटा — उत्तर बाएँ आधे में होगा, तो high नीचे करें।
• अगर बड़ा — दाएँ आधे में होगा, तो low ऊपर करें।

हर तुलना बचे का आधा हटाती है। यही पूरी तरकीब है।

Iterative program

#include <stdio.h>
int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key)      return mid;   // mil gaya
        else if (a[mid] < key)  low = mid + 1; // daayein jaayein
        else                    high = mid - 1; // baayein jaayein
    }
    return -1;                  // nahi mila
}
int main() {
    int a[] = {10, 20, 30, 40, 50};
    int pos = binarySearch(a, 5, 40);
    if (pos != -1) printf("Found at index %d\n", pos);
    else           printf("Not found\n");
    return 0;
}

Dry run

{10, 20, 30, 40, 50} में 40 ढूँढना:

चार के बजाय सिर्फ़ दो comparisons — और array बड़ा होते ही अंतर विशाल हो जाता है।

Recursive program

int binarySearch(int a[], int low, int high, int key) {
    if (low > high) return -1;              // base case
    int mid = low + (high - low) / 2;
    if (a[mid] == key)     return mid;
    if (a[mid] < key)      return binarySearch(a, mid + 1, high, key);
    else                   return binarySearch(a, low, mid - 1, key);
}

वही logic, loop के बजाय चुने आधे पर खुद को call करके व्यक्त।

यह इतना तेज़ क्यों है

चूँकि हर कदम data आधा करता है, binary search O(log n) में चलता है — दस लाख items को सिर्फ़ लगभग बीस जाँच चाहिए।

आम गलतियाँ

• Unsorted array पर चलाना — परिणाम निरर्थक होता है।
• (low + high) / 2 इस्तेमाल करना, जो overflow कर सकता है; low + (high - low) / 2 पसंद करें।
• गलत loop condition — यह low <= high होनी चाहिए, < नहीं।
• mid + 1 / mid - 1 से mid के आगे बढ़ना भूलना, जिससे infinite loop होता है।

सारांश

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