द्विआधारी खोज प्रणाली

द्विआधारी खोज प्रणाली (अंग्रेज़ी: Binary Search Algorithm) हल सारणी में किसी आइटम की स्थिति ढूंढती है। द्विआधारी खोज  तत्व सारणी के लिए एक इनपुट मूल्य की तुलना करके काम करता है। तुलना से यह निर्धारित होता  है कि इनपुट तत्व से कम या अधिक है। जब इनपुट, तत्व के बराबर हो जाता है तब खोज बंद हो जाती है और तत्व की स्थिति देता है। अगर तत्व इनपुट के समान नहीं है तो फिर पुन: एक और  तुलना करके पता लगाया जाता है कि इनपुट तत्व से छोटा है या तत्व से अधिक है। यदि इनपुट सारणी के भीतर स्थित नहीं है तो यह एल्गोरिथ्म आम तौर पर एक अद्वितीय मान दर्शाती है। द्विआधारी खोज एल्गोरिथ्म आमतौर पर संख्या की तुलना, सारणी को आधा करके उसके तत्वो से करती है। इस प्रकार दिए गए तत्व का पता लगाने मे लघुगणक समय लगता है। एक द्विआधारी खोज एक विभाजित और विजय खोज एल्गोरिथ्म है।

द्विआधारी खोज प्रणाली कैसे काम करता है?

१. प्रारम्भिक चरण:

• दो सूचक निर्धारित करें: निम्न और उच्च
• यह सारणी की शुरुआत और अन्त को दर्शाते हैं।

२. मध्य मान निकालना:

• वर्तमान सीमा का मध्य स्थान निकालें: मध्य = (निम्न + उच्च) / 2

३. तुलना करना:

• यदि मध्य स्थान पर रखा तत्व लक्ष्य के बराबर हो → खोज पूरी हो जाती है।
• यदि लक्ष्य, मध्य तत्व से छोटा हो → उच्च = मध्य – 1 (अर्थात बाएँ भाग में खोज जारी रखें)
• यदि लक्ष्य, मध्य तत्व से बड़ा हो → निम्न = मध्य + 1 (अर्थात दाएँ भाग में खोज करें)

४. प्रक्रिया दोहराना:

• इस प्रक्रिया को तब तक दोहराएँ जब तक:
  • लक्ष्य मिल न जाए, या
  • खोज क्षेत्र समाप्त न हो जाए (निम्न > उच्च)

द्विआधारी खोज का कार्यान्वयन

BinarySearch(A[0..N-1], value, low, high) {
 if (high < low)
 return -1 // not found
 mid = low + ((high - low) / 2)
 if (A[mid] > value)
 return BinarySearch(A, value, low, mid-1)
 else if (A[mid] < value)
 return BinarySearch(A, value, mid+1, high)
 else
 return mid // found
 }

बाहरी कड़ियाँ

• द्विआधारी खोज प्रणाली
• सी प्लस प्लस कार्यक्रम के माध्यम से द्विआधारी खोज प्रणाली