C भाषा में बाइनरी सर्च एल्गोरिदम

बाइनरी सर्च क्या है?

बाइनरी सर्च केवल सॉर्ट की गई सूची पर लागू होता है। सूची को दो बराबर भागों में बांटा जाता है और खोजी जाने वाली की (key) की तुलना मध्य एलिमेंट से की जाती है।

तीन संभावित स्थितियां

1. मध्य एलिमेंट == की: खोज सफलतापूर्वक समाप्त।
2. मध्य एलिमेंट > की: बाएं भाग में खोज जारी।
3. मध्य एलिमेंट < की: दाएं भाग में खोज जारी।

एल्गोरिदम

low = 0, high = n-1
while (low <= high) {
    mid = (low + high) / 2
    if (a[mid] == key) {
        flag = 1; break;
    } else if (a[mid] > key)
        high = mid - 1;
    else
        low = mid + 1;
}

C प्रोग्राम

#include <stdio.h>

int main() {
    int a[50], n, i, key, flag = 0, low, mid, high;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter sorted elements: ");
    for(i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("Enter key to search: ");
    scanf("%d", &key);
    low = 0; high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == key) {
            flag = 1; break;
        } else if (a[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    if (flag == 1)
        printf("Search successful");
    else
        printf("Search unsuccessful");
    return 0;
}

आउटपुट

Enter number of elements: 5
Enter sorted elements: 23 45 57 89 90
Enter key element: 45
Search successful

समय जटिलता

बाइनरी सर्च की समय जटिलता O(log n) होती है, जो रैखिक खोज (O(n)) से कहीं बेहतर है।