खोज…
द्विआधारी खोज
परिचय
बाइनरी सर्च एक डिवाइड और कॉन्कर सर्च एल्गोरिथ्म है। यह खोज स्थान में किसी तत्व का स्थान खोजने के लिए O(log n) समय का उपयोग करता है जहां n खोज स्थान का आकार है।
द्विआधारी खोज खोज स्थान के मध्य मूल्य के लिए लक्ष्य मूल्य की तुलना करने के बाद प्रत्येक पुनरावृत्ति पर खोज स्थान को आधा करके काम करता है।
बाइनरी सर्च का उपयोग करने के लिए, खोज स्थान को किसी तरह से क्रमबद्ध (क्रमबद्ध) किया जाना चाहिए। डुप्लिकेट प्रविष्टियाँ (वे जो तुलनात्मक फ़ंक्शन के अनुसार बराबर होती हैं) को प्रतिष्ठित नहीं किया जा सकता है, हालांकि वे बाइनरी सर्च प्रॉपर्टी का उल्लंघन नहीं करते हैं।
परंपरागत रूप से, हम तुलना फ़ंक्शन के रूप में (<) से कम का उपयोग करते हैं। यदि <b, यह सही वापस आ जाएगा। यदि a, b और b से कम नहीं है, तो a और b बराबर नहीं हैं।
उदाहरण प्रश्न
आप एक अर्थशास्त्री हैं, हालांकि एक बहुत बुरा है। आपको चावल के लिए संतुलन कीमत (यानी वह मूल्य, जहां आपूर्ति = मांग) की खोज का काम दिया जाता है।
याद रखें कि कीमत जितनी अधिक होगी, आपूर्ति उतनी ही बड़ी होगी और मांग कम होगी
जैसा कि आपकी कंपनी बाजार की शक्तियों की गणना में बहुत कुशल है, आप चावल की इकाइयों में आपूर्ति और मांग को तुरंत प्राप्त कर सकते हैं जब चावल की कीमत एक निश्चित मूल्य p पर सेट होती है।
आपका बॉस समान मूल्य एएसएपी चाहता है, लेकिन आपको बताता है कि संतुलन मूल्य एक सकारात्मक पूर्णांक हो सकता है जो कि अधिकतम 10^17 और रेंज में बिल्कुल 1 सकारात्मक पूर्णांक समाधान होने की गारंटी है। ताकि आप इसे खोने से पहले अपनी नौकरी के साथ जा रहे हैं!
आपको getSupply(k) और getDemand(k) फ़ंक्शन को कॉल करने की अनुमति है, जो वास्तव में समस्या में बताया गया है।
उदाहरण स्पष्टीकरण
यहां हमारा खोज स्थान 1 से 10^17 । इस प्रकार एक रेखीय खोज संभव है।
हालाँकि, ध्यान दें कि जैसे ही k ऊपर जाता है, getSupply(k) बढ़ता है और getDemand(k) घटता जाता है। इस प्रकार, किसी भी x > y , getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) । इसलिए, यह खोज स्थान मोनोटोनिक है और हम बाइनरी सर्च का उपयोग कर सकते हैं।
निम्न psuedocode बाइनरी खोज के उपयोग को प्रदर्शित करता है:
high = 100000000000000000 <- Upper bound of search space
low = 1 <- Lower bound of search space
while high - low > 1
mid = (high + low) / 2 <- Take the middle value
supply = getSupply(mid)
demand = getDemand(mid)
if supply > demand
high = mid <- Solution is in lower half of search space
else if demand > supply
low = mid <- Solution is in upper half of search space
else <- supply==demand condition
return mid <- Found solution
यह एल्गोरिथ्म ~O(log 10^17) समय में चलता है। यह करने के लिए सामान्यीकृत किया जा सकता ~O(log S) समय जहां एस के हर यात्रा पर के बाद से खोज अंतरिक्ष के आकार है while करने के लिए या तो [कम: मध्य] या: पाश, हम खोज अंतरिक्ष आधा कर दिया ([उच्च कम] से [mid: high] )।
C रिकर्सन के साथ बाइनरी सर्च का कार्यान्वयन
int binsearch(int a[], int x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid]) {
return (mid);
} else
if (x < a[mid]) {
binsearch(a, x, low, mid - 1);
} else {
binsearch(a, x, mid + 1, high);
}
}
बाइनरी खोज: क्रमबद्ध संख्याओं पर
छद्म कोड का उपयोग करके संख्याओं पर एक द्विआधारी खोज दिखाना सबसे आसान है
int array[1000] = { sorted list of numbers };
int N = 100; // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for
low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found
समानता के लिए सरणी [मध्य] से x की तुलना करके जल्दी लौटने का प्रयास न करें। अतिरिक्त तुलना केवल कोड को धीमा कर सकती है। ध्यान दें कि पूर्णांक विभाजन द्वारा हमेशा नीचे की ओर फँसने से बचने के लिए आपको एक को कम करने की आवश्यकता है।
दिलचस्प है, द्विआधारी खोज के उपरोक्त संस्करण आपको सरणी में एक्स की सबसे छोटी घटना खोजने की अनुमति देता है। यदि सरणी में x के डुप्लिकेट हैं, तो एल्गोरिथ्म को थोड़ा संशोधित किया जा सकता है ताकि इसके लिए x की सबसे बड़ी घटना को वापस लौटाया जा सके यदि केवल सशर्त को जोड़कर:
while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}
ध्यान दें कि mid = (low + high) / 2 करने के बजाय, कार्यान्वयन के लिए mid = low + ((high - low) / 2) का प्रयास करना एक अच्छा विचार हो सकता है जैसे कि जावा कार्यान्वयन के जोखिम को कम करने के लिए वास्तव में बड़े इनपुट के लिए अतिप्रवाह।
रैखिक खोज
रैखिक खोज एक सरल एल्गोरिथ्म है। यह आइटम के माध्यम से लूप करता है जब तक कि क्वेरी नहीं मिली है, जो इसे एक रैखिक एल्गोरिथ्म बनाता है - जटिलता ओ (एन) है, जहां n से गुजरने के लिए मदों की संख्या है।
क्यों ओ (एन)? सबसे खराब स्थिति में, आपको सभी एन आइटमों से गुजरना होगा।
इसकी तुलना किताबों के ढेर में एक किताब की तलाश में की जा सकती है - आप उन सभी से गुजरते हैं जब तक कि आपको वह नहीं मिल जाता जो आप चाहते हैं।
नीचे पायथन कार्यान्वयन है:
def linear_search(searchable_list, query):
for x in searchable_list:
if query == x:
return True
return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True
राबिन कार्प
राबिन-कार्प एल्गोरिथ्म या कार्प-राबिन एल्गोरिथ्म एक स्ट्रिंग खोज एल्गोरिथ्म है जो किसी टेक्स्ट में पैटर्न स्ट्रिंग्स के सेट में से किसी एक को खोजने के लिए हैशिंग का उपयोग करता है। औसत और सबसे अच्छा केस रनिंग टाइम O (n + m) स्पेस O में है ( p), लेकिन इसका सबसे खराब समय O (nm) है जहां n पाठ की लंबाई और m पैटर्न की लंबाई है।
स्ट्रिंग मिलान के लिए जावा में एल्गोरिदम कार्यान्वयन
void RabinfindPattern(String text,String pattern){
/*
q a prime number
p hash value for pattern
t hash value for text
d is the number of unique characters in input alphabet
*/
int d=128;
int q=100;
int n=text.length();
int m=pattern.length();
int t=0,p=0;
int h=1;
int i,j;
//hash value calculating function
for (i=0;i<m-1;i++)
h = (h*d)%q;
for (i=0;i<m;i++){
p = (d*p + pattern.charAt(i))%q;
t = (d*t + text.charAt(i))%q;
}
//search for the pattern
for(i=0;i<end-m;i++){
if(p==t){
//if the hash value matches match them character by character
for(j=0;j<m;j++)
if(text.charAt(j+i)!=pattern.charAt(j))
break;
if(j==m && i>=start)
System.out.println("Pattern match found at index "+i);
}
if(i<end-m){
t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
if(t<0)
t=t+q;
}
}
}
हैश मान की गणना करते समय हम टकराव से बचने के लिए इसे एक प्रमुख संख्या से विभाजित कर रहे हैं। अभाज्य संख्या से विभाजित करने के बाद टक्कर की संभावना कम होगी, लेकिन फिर भी चिकित्सा एक मौका है कि हैश मान दो तारों के लिए समान हो सकता है, इसलिए जब हमें एक मैच मिलता है, हमें यह सुनिश्चित करने के लिए चरित्र द्वारा चरित्र की जांच करनी होगी कि हमें उचित मैच मिला है।
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m):% q;
यह पैटर्न के लिए हैश मान को पुनर्गठित करना है, पहले बाएं चरित्र को हटाकर और फिर पाठ से नए चरित्र को जोड़ना।
रैखिक खोज का विश्लेषण (सबसे खराब, औसत और सर्वोत्तम मामले)
एक एल्गोरिथ्म का विश्लेषण करने के लिए हमारे पास तीन मामले हो सकते हैं:
सबसे खराब मामला
औसत केस
सबसे अच्छा मामला
#include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 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[] = {1, 10, 30, 15}; int x = 30; int n = sizeof(arr)/sizeof(arr[0]); printf("%d is present at index %d", x, search(arr, n, x)); getchar(); return 0; }
सबसे खराब मामला विश्लेषण (आमतौर पर किया गया)
सबसे खराब स्थिति के विश्लेषण में, हम एक एल्गोरिथ्म के चलने के समय की ऊपरी सीमा की गणना करते हैं। हमें उस मामले को जानना चाहिए, जिसके कारण अधिकतम संख्या में संचालन निष्पादित होता है। रैखिक खोज के लिए, सबसे खराब स्थिति तब होती है जब खोजा जाने वाला तत्व (उपरोक्त कोड में x) सरणी में मौजूद नहीं है। जब x मौजूद नहीं होता है, तो खोज () फ़ंक्शन इसकी गिरफ्तारी के सभी तत्वों के साथ तुलना करता है [] एक-एक करके। इसलिए, रैखिक खोज की सबसे खराब स्थिति समय जटिलता n (n) होगी
औसत केस विश्लेषण (कभी-कभी किया जाता है)
औसत मामले के विश्लेषण में, हम सभी संभव इनपुट लेते हैं और सभी इनपुट के लिए कंप्यूटिंग समय की गणना करते हैं। सभी परिकलित मानों को जोड़ दें और योग को कुल संख्याओं से विभाजित करें। हमें मामलों के वितरण का पता (या भविष्यवाणी) करना चाहिए। रैखिक खोज समस्या के लिए, मान लें कि सभी मामले समान रूप से वितरित किए गए हैं (x का मामला सरणी में मौजूद नहीं होने सहित)। इसलिए हम सभी मामलों को जोड़ते हैं और योग को (n + 1) से विभाजित करते हैं। निम्नलिखित औसत केस टाइम जटिलता का मूल्य है।
सर्वश्रेष्ठ केस विश्लेषण (बोगस)
सर्वोत्तम मामले के विश्लेषण में, हम एक एल्गोरिथ्म के चलने के समय की कम बाध्यता की गणना करते हैं। हमें उस मामले को जानना चाहिए जो कम से कम संचालन को निष्पादित करता है। रैखिक खोज समस्या में, सबसे अच्छा मामला तब होता है जब x पहले स्थान पर मौजूद होता है। सर्वोत्तम मामले में संचालन की संख्या निरंतर है (एन पर निर्भर नहीं है)। तो सबसे अच्छे मामले में समय की जटिलता complex (1) सबसे अधिक होगी, हम एल्गोरिदम का विश्लेषण करने के लिए सबसे खराब स्थिति विश्लेषण करते हैं। सबसे खराब विश्लेषण में, हम एक एल्गोरिथ्म के चल रहे समय पर एक ऊपरी सीमा की गारंटी देते हैं जो अच्छी जानकारी है। औसत केस विश्लेषण अधिकांश व्यावहारिक मामलों में करना आसान नहीं है और यह शायद ही कभी किया जाता है। औसत मामले के विश्लेषण में, हमें सभी संभावित आदानों के गणितीय वितरण को जानना (या भविष्यवाणी करना) चाहिए। बेस्ट केस विश्लेषण फर्जी है। एक एल्गोरिथ्म पर एक निचली सीमा की गारंटी देना सबसे बुरी स्थिति में कोई जानकारी प्रदान नहीं करता है, एक एल्गोरिथ्म को चलाने में कई साल लग सकते हैं।
कुछ एल्गोरिदम के लिए, सभी मामले समान रूप से समान हैं, अर्थात, सबसे खराब और सबसे अच्छे मामले नहीं हैं। उदाहरण के लिए, मर्ज सॉर्ट। मर्ज सॉर्ट सभी मामलों में ge (nLogn) संचालन करता है। अन्य छँटाई वाले अधिकांश एल्गोरिदम में सबसे खराब और सबसे अच्छे मामले हैं। उदाहरण के लिए, क्विक सॉर्ट के विशिष्ट कार्यान्वयन में (जहां धुरी को कोने के तत्व के रूप में चुना जाता है), सबसे खराब तब होता है जब इनपुट सरणी पहले से ही सॉर्ट की जाती है और सबसे अच्छा तब होता है जब धुरी तत्व हमेशा सरणी को दो हिस्सों में विभाजित करते हैं। सम्मिलन प्रकार के लिए, सबसे खराब स्थिति तब होती है जब सरणी को उल्टा क्रमबद्ध किया जाता है और सबसे अच्छा मामला तब होता है जब उत्पादन के दौरान उसी क्रम में सरणी को क्रमबद्ध किया जाता है।