যখন তালিকাটি সাজানো হয় তখন আমরা তালিকার আইটেমগুলি খুঁজে পেতে বাইনারি অনুসন্ধান কৌশল ব্যবহার করতে পারি। এই পদ্ধতিতে, পুরো তালিকাটিকে দুটি উপ-তালিকায় বিভক্ত করা হয়েছে। যদি আইটেমটি মাঝের অবস্থানে পাওয়া যায়, তবে এটি অবস্থানটি ফেরত দেয়, অন্যথায় বাম বা ডান উপ-তালিকায় লাফ দেয় এবং আইটেমটি খুঁজে না পাওয়া পর্যন্ত বা পরিসীমা অতিক্রম না করা পর্যন্ত একই প্রক্রিয়াটি আবার করে।
বাইনারি সার্চ টেকনিকের জটিলতা
- সময়ের জটিলতা : O(1) সেরা ক্ষেত্রে। O(log2 n) গড় বা সবচেয়ে খারাপ ক্ষেত্রে।
- স্পেস জটিলতা: O(1)
ইনপুট এবং আউটপুট
Input: A sorted list of data: 12 25 48 52 67 79 88 93 The search key 79 Output: Item found at location: 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); //mid location of the list
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]; //create an array of size 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
