जब लिस्ट सॉर्टेड होती है तो हम लिस्ट में आइटम्स खोजने के लिए बाइनरी सर्च तकनीक का उपयोग कर सकते हैं। इस प्रक्रिया में, पूरी लिस्ट को दो सब-लिस्ट में विभाजित किया जाता है। यदि आइटम मध्य स्थिति में मिलता है, तो यह स्थान वापस करता है, अन्यथा बाएं या दाएं सब-लिस्ट में कूदता है और वही प्रक्रिया तब तक दोहराता है जब तक आइटम न मिल जाए या रेंज पार न हो जाए।
बाइनरी सर्च तकनीक की जटिलता
- समय जटिलता: बेस्ट केस के लिए O(1)। औसत या वर्स्ट केस के लिए O(log₂ n)।
- स्पेस जटिलता: O(1)
इनपुट और आउटपुट
इनपुट: सॉर्टेड डेटा की सूची: 12 25 48 52 67 79 88 93 खोज कुंजी 79 आउटपुट: आइटम स्थान पर मिला: 5
एल्गोरिदम
binarySearch(array, start, end, key)
इनपुट - एक सॉर्टेड सरणी, प्रारंभ और अंत स्थान, और खोज कुंजी
आउटपुट - कुंजी का स्थान (यदि मिला), अन्यथा गलत स्थान।
Begin if start <= end then mid := start + (end - start) /2 if array[mid] = key then return mid location if array[mid] > key then call binarySearch(array, mid+1, end, key) else when array[mid] < key then call binarySearch(array, start, mid-1, key) else return invalid location End
उदाहरण
#include<iostream> using namespace std; int binarySearch(int array[], int start, int end, int key) { if(start <= end) { int mid = (start + (end - start) /2); //लिस्ट का मिड स्थान if(array[mid] == key) return mid; if(array[mid] > key) return binarySearch(array, start, mid-1, key); return binarySearch(array, mid+1, end, key); } return -1; } int main() { int n, searchKey, loc; cout << "Enter number of items: "; cin >> n; int arr[n]; //आकार n की सरणी बनाएं cout << "Enter items: " << endl; for(int i = 0; i< n; i++) { cin >> arr[i]; } cout << "Enter search key to search in the list: "; cin >> searchKey; if((loc = binarySearch(arr, 0, n, searchKey)) >= 0) cout << "Item found at location: " << loc << endl; else cout << "Item is not found in the list." << endl; }आउटपुट
Enter number of items: 8 Enter items: 12 25 48 52 67 79 88 93 Enter search key to search in the list: 79 Item found at location: 5
