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

इस ट्यूटोरियल में, आप सीखेंगे कि बाइनरी सर्च कैसे काम करता है। इसके अलावा, आप सी, सी ++, जावा और पायथन में बाइनरी सर्च के काम के उदाहरण पाएंगे।

बाइनरी खोज एक सॉर्ट किए गए सरणी में एक तत्व की स्थिति खोजने के लिए एक खोज एल्गोरिथ्म है।

इस दृष्टिकोण में, तत्व हमेशा एक सरणी के एक हिस्से के बीच में खोजा जाता है।

बाइनरी खोज को केवल वस्तुओं की छँटाई सूची पर लागू किया जा सकता है। यदि तत्वों को पहले से ही हल नहीं किया गया है, तो हमें उन्हें पहले क्रमबद्ध करना होगा।

बाइनरी सर्च वर्किंग

बाइनरी सर्च एल्गोरिथ्म को दो तरीकों से लागू किया जा सकता है, जो नीचे चर्चा की गई है।

  1. Iterative विधि
  2. पुनरावर्ती विधि

पुनरावर्ती विधि विभाजन और विजय दृष्टिकोण का अनुसरण करती है।

दोनों विधियों के सामान्य चरणों की चर्चा नीचे की गई है।

  1. जिस सरणी में खोज की जानी है वह है: आरंभिक सरणी खोजा जाने वाला तत्व होने
    दें x = 4।
  2. क्रमशः सबसे कम और उच्चतम स्थिति में दो पॉइंटर्स कम और उच्च सेट करें। पॉइंटर्स सेट करना
  3. सरणी के मध्य तत्व को खोजें अर्थात। (arr(low + high)) / 2 = 6। मध्य तत्व
  4. यदि x == मध्य है, तो मध्य में लौटें। ठीक है, m के साथ खोजे जाने वाले तत्व की तुलना करें।
  5. यदि x> mid, x को मध्य के दाईं ओर तत्वों के मध्य तत्व के साथ तुलना करें। यह निम्न पर सेट करके किया जाता है low = mid + 1।
  6. एल्स, एक्स की तुलना मध्य के बाईं ओर तत्वों के मध्य तत्व के साथ करें। यह उच्च सेटिंग के द्वारा किया जाता है high = mid - 1। मध्य तत्व को खोजना
  7. चरण 3 से 6 तक दोहराएं जब तक कि कम उच्च को पूरा नहीं करता। मध्य तत्व
  8. x = 4पाया जाता है। मिल गया

बाइनरी खोज एल्गोरिथम

Iteration विधि

जब तक संकेत कम और उच्च एक दूसरे से मिलते हैं। मध्य = (निम्न + उच्च) / 2 यदि (x == गिरफ्तारी) बाईं ओर ऊँची = मध्य - १

पुनरावर्ती विधि

 बाइनरीसर्च (गिरफ्तारी, x, निम्न, उच्च) यदि निम्न> उच्च वापसी गलत है तो दूसरा मध्य = (निम्न + उच्च) / 2 यदि x = गिरफ्तारी (मध्य) x के बीच में लौटता है तो x <डेटा (मध्य) // x चालू है दाईं ओर वापसी बाइनरीसर्च (गिरफ्तारी, x, मध्य + 1, उच्च) और // x दाईं ओर वापसी द्विआधारी खोज (गिरफ्तारी, x, निम्न, मध्य - 1) है

पायथन, जावा, C / C ++ उदाहरण (Iterative Method)

पायथन जावा सी सी ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

पायथन, जावा, C / C ++ उदाहरण (पुनरावर्ती विधि)

पायथन जावा सी सी ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

द्विआधारी खोज जटिलता

समय की जटिलताएँ

  • सबसे अच्छा मामला जटिलता :O(1)
  • औसत मामला जटिलता :O(log n)
  • सबसे खराब मामला जटिलता :O(log n)

अंतरिक्ष की जटिलता

बाइनरी खोज की अंतरिक्ष जटिलता है O(n)।

बाइनरी सर्च एप्लीकेशन

  • जावा, .Net, C ++ STL के पुस्तकालयों में
  • डिबगिंग करते समय, द्विआधारी खोज का उपयोग उस स्थान को इंगित करने के लिए किया जाता है जहां त्रुटि होती है।

दिलचस्प लेख...