C भाषा में खोज तकनीकें (Searching Techniques)

खोज (Searching) का परिचय

खोज तकनीक का अर्थ है किसी सूची में किसी कुंजी तत्व (key element) को ढूंढना। यदि तत्व मिल जाता है तो खोज सफल (successful), अन्यथा असफल (unsuccessful) होती है।

C में दो प्रमुख खोज तकनीकें

1. रैखिक खोज (Linear Search)
2. द्विआधारी खोज (Binary Search)

1. रैखिक खोज (Linear Search)

• सबसे सरल खोज विधि।
• तत्वों को एक-एक करके क्रमबद्ध तरीके से जांचा जाता है।
• सूची का क्रमबद्ध (sorted) होना आवश्यक नहीं।
• समय जटिलता: O(n) - बड़े डेटा के लिए धीमी।

एल्गोरिदम

1. सूची के पहले तत्व से शुरू करें।
2. प्रत्येक तत्व की तुलना कुंजी से करें।
3. मिलने पर सूचकांक लौटाएं।
4. अंत तक न मिलने पर -1 या असफलता संदेश दें।

C प्रोग्राम: रैखिक खोज

#include <stdio.h>

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key)
            return i;  // मिल गया, सूचकांक लौटाएं
    }
    return -1;  // नहीं मिला
}

int main() {
    int n, key;
    printf("तत्वों की संख्या: ");
    scanf("%d", &n);
    
    int arr[n];
    printf("%d तत्व दर्ज करें:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    
    printf("खोजने वाला तत्व: ");
    scanf("%d", &key);
    
    int result = linearSearch(arr, n, key);
    if (result != -1)
        printf("तत्व सूचकांक %d पर मिला।\n", result);
    else
        printf("तत्व नहीं मिला।\n");
    
    return 0;
}

2. द्विआधारी खोज (Binary Search)

• केवल क्रमबद्ध (sorted) सूची पर काम करता है।
• सूची को बार-बार आधा करके खोजता है।
• समय जटिलता: O(log n) - रैखिक खोज से बहुत तेज।

एल्गोरिदम

1. निम्न (low=0) और उच्च (high=n-1) सूचकांक सेट करें।
2. मध्य (mid = (low+high)/2) निकालें।
3. यदि arr[mid] == key → मिल गया।
4. यदि key < arr[mid] → high = mid-1 (बाएं आधे में खोजें)।
5. यदि key > arr[mid] → low = mid+1 (दाएं आधे में खोजें)।
6. low > high होने तक दोहराएं।

C प्रोग्राम: द्विआधारी खोज

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key)
            return mid;
        else if (key < arr[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

int main() {
    int n, key;
    printf("क्रमबद्ध तत्वों की संख्या: ");
    scanf("%d", &n);
    
    int arr[n];
    printf("क्रमबद्ध क्रम में %d तत्व दर्ज करें:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    
    printf("खोजने वाला तत्व: ");
    scanf("%d", &key);
    
    int result = binarySearch(arr, n, key);
    if (result != -1)
        printf("तत्व सूचकांक %d पर मिला।\n", result);
    else
        printf("तत्व नहीं मिला।\n");
    
    return 0;
}

तुलना