This post is also available in: English العربية (Arabic)
इस लेख में, हम 5 महत्वपूर्ण सर्च एल्गोरिदम पर चर्चा करेंगे। सर्च और सॉर्टएल्गोरिदम लगभग सभी ऍप्लिकेशन्स का एक महत्वपूर्ण हिस्सा होते हैं। लेख पढ़ें और अंत में एक प्रश्नोत्तरी में प्रश्नों के उत्तर दें।
सर्च एल्गोरिथ्म क्या है?
एक खोज एल्गोरिथ्म एक कदम-दर-चरण प्रक्रिया है जिसका उपयोग संगृहीत डेटा के संग्रह से विशिष्ट डेटा का पता लगाने के लिए किया जाता है। इसे कंप्यूटिंग में एक मौलिक प्रक्रिया माना जाता है। कंप्यूटर विज्ञान में, डेटा की खोज करते समय, एक तेज़ एप्लिकेशन और धीमी गति के बीच का अंतर अक्सर उचित सर्च एल्गोरिदम के उपयोग में निहित होता है।
सभी सर्च एल्गोरिदम खोज प्रक्रिया को आगे बढ़ाने के लिए खोज कुंजी (सर्च की) का उपयोग करते हैं। सर्च एल्गोरिदम में खोजे गए डाटा की सफलता या विफलता की स्थिति आमतौर पर बूलियन वैल्यू (ट्रू / फॉल्स) द्वारा दर्शायी जाती है। विभिन्न प्रकार के खोज एल्गोरिदम उपलब्ध हैं, और इन एल्गोरिदम का प्रदर्शन और दक्षता डेटा की मात्रा और उनके उपयोग करने के तरीके पर निर्भर करती है।
किसी भी एल्गोरिथ्म का चयन करते समय माना जाता है कि कई अन्य कारणों के अलावा दो मुख्य महत्वपूर्ण कारक समय और मेमोरी हैं। एक एल्गोरिथम ऐसा होना चाहिए जो कार्य को पूरा करने के लिए कम समय ले (टाइम फैक्टर) और साथ ही प्रक्रिया को न्यूनतम स्थान का उपयोग करे (स्पेस फैक्टर)।
सर्च एल्गोरिदम का उपयोग कहां किया जाता है?
खोज एल्गोरिदम किसी भी एप्लीकेशन का एक महत्वपूर्ण हिस्सा होते हैं। जब आप अपने सेल फोन से कॉल करते हैं, तो उसमें मौजूद सॉफ्टवेयर किसी विशेष फोन नंबर की खोज करता है और कॉल करता है। इसी तरह, जब आप अपने पसंदीदा सोशल मीडिया प्लेटफ़ॉर्म पर नाम टाइप कर रहे होते हैं, तो प्रोग्राम उस नाम को अपने विशाल डेटाबेस में खोजता है। आजकल हर कोई सर्च इंजिन्स जैसे Google, Bing इत्यादि से परिचित है। सर्च एल्गोरिदम इन सभी सर्च इंजनों का एक महत्वपूर्ण हिस्सा होते हैं। हम ऐसे किसी भी एप्लीकेशन के बारे में नहीं सोच सकते जहाँ सर्च एल्गोरिदम का उपयोग एक या दूसरे रूप में नहीं किया गया हो।
सर्च एल्गोरिदम के प्रकार
जैसा कि ऊपर उल्लेख किया गया है कि दो महत्वपूर्ण कारक हैं जिन्हें एल्गोरिथ्म का चयन करते समय ध्यान में रखा जाता है। डेटा की आवश्यकता और मात्रा के आधार पर, एक विशेष सर्च एल्गोरिदम का चयन किया जाता है। यहां हम 5 महत्वपूर्ण सर्च एल्गोरिदम पर चर्चा करेंगे।
- लीनियर सर्च (Linear Search)
- बाइनरी सर्च (Binary Search)
- जम्प सर्च (Jump Search)
- इन्टरपोलेशन सर्च (Interpolation Search)
- एक्सपोनेंशियल सर्च (Exponential Search)
लीनियर सर्च (Linear Search)
महत्वपूर्ण सर्च एल्गोरिदम की हमारी सूची में पहला लीनियर सर्च है। लीनियर सर्च एक बहुत ही सरल सर्च एल्गोरिथ्म है। इस प्रकार की खोज (सर्च) में, एक के बाद एक सभी वस्तुओं पर अनुक्रमिक खोज की जाती है। प्रत्येक आइटम की जाँच की जाती है और यदि कोई मिलान पाया जाता है तो उस विशेष आइटम को अंकित कर दिया जाता है, अन्यथा, डेटा संग्रह के अंत तक खोज जारी रहती है। यदि डेटा संग्रह के अंत तक आइटम नहीं मिलता है, तो एल्गोरिथ्म एक बूलियन मान लौटाता है जिसका अर्थ है ‘फॉल्स’ अर्थात “आइटम नहीं मिला” होता है।
लीनियर सर्च कैसे कार्य करता है?
लीनियर सर्च में निम्न चरणों द्वारा कार्य पूर्ण होता है:
- बूलियन चर (वेरिएबल) को ‘फॉल्स’ इनिशियलाइज़ करें।
- किसी सरणी के सबसे बाएं (पहले) एलिमेंट से शुरू करें और एक-एक करके उस एलिमेंट की तुलना, जिसे हम खोज रहे हैं, सरणी के प्रत्येक एलिमेंट के साथ करें।
- यदि हम उस एलिमेंट और सरणी के वर्तमान एलिमेंट के बीच एक मेल पाते हैं, तो एलिमेंट की स्थिति नोट की जाती है और बूलियन चर (वैरिएबल) की वैल्यू ‘ट्रू’ मार्क कर दी जाती है।
- यदि बूलियन चर कि वैल्यू “फॉल्स” होती है,तो एलिमेंट नहीं मिला।
लीनियर सर्च का एल्गोरिथ्म
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
C ++ में लीनियर कोड के लिए कोड
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main()
{
int arr[] = { 3, 4, 1, 7, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int index = search(arr, n, x);
if (index == -1)
cout << "Element is not present in the array";
else
cout << "Element found at position " << index;
return 0;
}
बाइनरी सर्च (Binary Search)
बाइनरी खोज सॉर्ट किए गए डेटा के लिए एक व्यापक रूप से उपयोग किया जाने वाला एल्गोरिदम है और इसलिए महत्वपूर्ण सर्च एल्गोरिदम की सूची में एक और है। बाइनरी सर्च एक उन्नत प्रकार का सर्च एल्गोरिथ्म है जो वस्तुओं की क्रमबद्ध सूची से डेटा प्राप्त करता है। इसके मुख्य कार्य सिद्धांत में सूची में सेट किए गए डेटा को आधे में विभाजित करना शामिल है जब तक आवश्यक डाटा आइटम मिल नहीं जाता। बाइनरी खोज को कभी-कभी हाफ-इंटरवल सर्च या एक लघुगणक (लोगरिथ्मिक) सर्च भी कहा जाता है।
बाइनरी सर्च कैसे कार्य करता है?
बाइनरी सर्च निम्न चरणों का पालन करता है:
खोज प्रक्रिया डेटा के क्रमबद्ध सरणी के मध्य स्थित एलिमेंट का पता लगाकर आरंभ करती है।
- बूलियन चर (वेरिएबल) को ‘फॉल्स’ इनिशियलाइज़ करें।
- वर्तमान एलिमेंट (करंट एलिमेंट) के साथ की वैल्यू (जिसे खोजा जाना है) से तुलना की जाती है।
- यदि की वैल्यू मध्य स्थित एलिमेंट से अधिक है, तो खोज तुलना और मिलान के लिए मध्य तत्व के ऊपरी वैल्यूज का विश्लेषण करती है।
- यदि की वैल्यू मध्य स्थित एलिमेंट से कम है, तो खोज तुलना और मिलान के लिए मध्य तत्व के निचली वैल्यूज का विश्लेषण करती है।
- यदि की वैल्यू मध्य स्थित एलिमेंट बराबर है, तो इसका मतलब है कि खोजे जाने वाला एलिमेंट मिल गया और बूलियन चर (वेरिएबल) को “ट्रू” बना दिया जाता है।
- यदि बूलियन चर कि वैल्यू “फॉल्स” होती है,तो एलिमेंट नहीं मिला।
बाइनरी सर्च के लिए एल्गोरिथ्म
Step 1: Set L to 0 and U to N and F to ‘False’
Step 2: MID = (L + U)/2
Step 3: if A[MID] = x, then Print Element x Found at index MID and set F to ‘True’ and goto step 6
Step 4: if A > x, U = MID – 1 and goto step 2[MID]
Step 5: if A[MID] < x, L = MID + 1 and goto step 2
Step 6: If F = ‘False’ then Print Element x Not Found
Step 7: Exit
C ++ में बाइनरी सर्च के लिए कोड
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
जम्प सर्च (Jump Search)
बाइनरी सर्च की तरह, जंप सर्च, (श्रेणीबद्ध) सॉर्ट किए गए सरणियों के लिए एक खोज एल्गोरिथ्म है। इस अल्गोरिथम का मूल विचार सभी एलिमेंट्स की खोज के स्थान पर कुछ कदमों को छोड़ कर या कुछ एलिमेंट्स को छोड़ कर कम एलिमेंट्स की (लीनियर सर्च से) जाँच करना है। यही कारण है कि यह महत्वपूर्ण सर्च एल्गोरिदम की सूची में एक स्थान रखता है।
मान लेते हैं कि 0 से n-1 तक के अनुक्रमणिका के साथ आकार n की एक सॉर्ट (क्रमबद्ध) की गयी सरणी A है, और तत्व x जिसे A में खोजा जाना है। इस एल्गोरिथ्म को लागू करने के लिए, आकार m के एक ब्लॉक की भी आवश्यकता होती है, जो कि हर पुनरावृत्ति में छोड़ दिया जाता है।
जम्प सर्च कैसे काम करता है?
यह एल्गोरिथ्म इस प्रकार काम करता है:
- Iteration 1: यदि x = A [0], तो सक्सेस (सफलता), अन्यथा यदि x> A [0], तो अगले ब्लॉक पर जाएं।
- Iteration 2: यदि x = A [m], तो सक्सेस (सफलता), अन्यथा, यदि x> A [m], तो अगले ब्लॉक पर जाएं।
- Iteration 3: यदि x = A[2m] then, तो सक्सेस (सफलता), अन्यथा, यदि x> A [2m] to, तो अगले ब्लॉक पर जाएं।
- किसी भी समय, यदि x[km] तो स्थिति A [(k – 1) m] से A तक एक लीनियर सर्च किया जाता है।[km]
जंप सर्च के लिए एल्गोरिदम
Step 1: Set i = 0 and m = sqrt(n).
Step 2: if A[i] != x and A[i] < x, then jump to the next block and set i = m and m = m + m.
Step 3: if m < n – 1 then goto step 2
Step 4: if A[i] > x, then move to the beginning of the current block and perform a linear search.
Step 5: Exit
C ++ में जंप सर्च के लिए कोड
int jumpSearch(int array[], int size, int key) {
int start = 0;
int end = sqrt(size);
while(array[end] <= key && end < size) {
start = end;
end += sqrt(size);
if(end > size - 1)
end = size;
}
for(int i = start; i<end; i++)
if(array[i] == key)
return i;
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[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 = jumpSearch(arr, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}
इन्टरपोलेशन सर्च (Interpolation Search)
इंटरपोलेशन सर्च एक अन्य महत्वपूर्ण सर्च एल्गोरिदम है। इंटरपोलेशन सर्च, बाइनरी सर्च का एक बेहतर संस्करण है। यह सर्च एल्गोरिथ्म खोजे जाने वाली वैल्यू की स्थिति (पोजीशन) पर काम करता है। इस एल्गोरिथम को ठीक से काम करने के लिए, डेटा संग्रह एक क्रमबद्ध रूप में और समान रूप से वितरित किया जाना चाहिए।
कुछ ऐसी भी स्तिथियाँ होती हैं जहां खोजे जाने वाले डेटा का स्थान पहले मालूम होता है। उदाहरण के लिए, टेलीफोन डायरेक्टरी के मामले में, यदि हम किसी विशेष व्यक्ति का टेलीफोन नंबर खोजना चाहते हैं, जिसका नाम ‘M’ से शुरू होता है। ऐसी स्थिति में, लीनियर सर्च और यहां तक कि बाइनरी सर्च धीमी लगती है क्योंकि हम सीधे मेमोरी स्पेस के उस लोकेशन पर पहुँच सकते हैं जहां ’M’ से शुरू होने वाले नाम संग्रहीत हैं।
बाइनरी सर्च के मामले में, यदि वांछित डेटा नहीं मिलता है, तो सूची के बाकी हिस्सों को दो भागों में विभाजित किया जाता है, निम्न और उच्चतर। फिर उनमें से किसी एक में खोज की जाती है। यदि डेटा सॉर्ट किया हुआ भी है, तो भी बाइनरी सर्च वांछित डेटा की स्थिति की जांच करने का लाभ नहीं उठाता है।
इन्टरपोलेशन सर्च कैसे कार्य करता है?
यह एल्गोरिथ्म इस प्रकार काम करता है:
- जांच स्थिति (प्रोब पोजीशन) की गणना करके इंटरपोलेशन सर्च एक विशेष वस्तु को खोजती है। प्रारंभ में, जांच स्थिति संग्रह के सबसे मध्य आइटम की स्थिति होती है।
- यदि एक मिलाप होता है, तो आइटम का सूचकांक नोट कर लिया जाता है। सूची को दो भागों में विभाजित करने के लिए, हम निम्नलिखित विधि का उपयोग करते हैं:
mid = Lo + ((Hi – Lo)/(A[Hi] – A[Lo])) * (x – A[Lo]), where
A is list
Lo is lowest index of the list
Hi is highest index of the list
A[n] is the value stored at index n in the list
- यदि मध्य आइटम, आइटम x (आइटम जिसे खोजा जाना है) से अधिक है, तो जांच की स्थिति फिर से मध्य आइटम के दाईं ओर उप-सरणी में की जाती है। अन्यथा, आइटम को मध्य आइटम के बाईं ओर उप-सरणी में खोजा जाता है। यह प्रक्रिया उप-सरणी पर तब तक जारी रहती है जब तक कि उप-सरणी का आकार शून्य से कम न हो जाए।
इंटरपोलेशन सर्च के लिए एल्गोरिदम
Step 1: Start searching data from the middle of the list and initialize boolean variable F to ‘False’.
Step 2: If it is a match, return the index of the item and move ‘True’ to F goto
Step 3: If it is not a match, probe position.
Step 4: Divide the list using a probing formula and find the new middle.
Step 5: If the data is greater than middle, search in higher sub-list.
Step 6: If data is smaller than the middle, search in the lower sub-list.
Step 7: If F = ‘False’ then Print Element x Not Found
Step 8: Exit
C ++ में इंटरपोलेशन सर्च के लिए कोड
int interpolationSearch(int array[], int start, int end, int key) {
int dist, valRange, indexRange, estimate;
float fraction;
while(start <= end && key >= array[start] && key <= array[end]) {
dist = key - array[start];
valRange = array[end] - array[start];
fraction = dist / valRange;
indexRange = end - start;
estimate = start + (fraction * indexRange);
if(array[estimate] == key)
return estimate;
if(array[estimate] < key)
start = estimate +1;
else
end = estimate - 1;
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[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 = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}
एक्सपोनेंशियल सर्च (Exponential Search)
महत्वपूर्ण सर्च एल्गोरिदम की सूची में अगला एक्सपोनेंशियल सर्च है। एक्सपोनेंशियल सर्च को डॉबलिंग (डॉबलिंग) या गललॉपिंग (गललॉपिंग) सर्च के रूप में भी जाना जाता है। इस तंत्र का उपयोग उस फैलाव (रेंज) को खोजने के लिए किया जाता है जहां खोज कुंजी मौजूद हो सकती है। यदि L और U सूची के निचले और ऊपरी सीमा हैं, तो L और U दोनों 2 की घात (पावर) हैं। अंतिम खंड के लिए, U सूची की अंतिम स्थिति (पोजीशन) है। इस कारण से, यह घातीय के रूप में जाना जाता है। विशिष्ट श्रेणी खोजने के बाद, यह खोज कुंजी का सही स्थान खोजने के लिए बाइनरी सर्च तकनीक का उपयोग करता है।
एक्सपोनेंशियल सर्च के लिए एल्गोरिथ्म
Step 1: Jump the array 2^i elements at a time searching for the condition Array[2^(i-1)] < valueWanted < Array[2^i].
Step 2: If 2^i is greater than the length of the array, then set the upper bound to the length of the array.
Step 3: Do a binary search between Array[2^(i-1)] and Array[2^i]
C ++ में एक्सपोनेंशियल सर्च के लिए कोड
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 exponentialSearch(int array[], int start, int end, int key){
if((end - start) <= 0)
return -1;
int i = 1;
while(i < (end - start)){
if(array[i] < key)
i *= 2;
else
break;
}
return binarySearch(array, i/2, i, key);
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[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 = exponentialSearch(arr, 0, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}
इमेज क्रेडिट: कंप्यूटर वेक्टर pch.vector द्वारा बनाया गया – www.freepik.com
