बाइनरी सी ++ में एक स्ट्रिंग खोजें

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

उदाहरण

Input : stringArray = {“I”, “Love”, “Programming”, “tutorials”, “point”}.
Element = “programming”
Output : string found at index 3
Explanation : The index of string is 3.
Input : stringArray = {“I”, “Love”, “Programming”, “tutorials”, “point”}.
Element = “coding”
Output : -1 ‘string not found’

द्विआधारी खोज खोज तकनीक है जो तत्व को खोजने के लिए सरणी के मध्य को ढूंढकर काम करती है।

स्ट्रिंग्स की सरणी के लिए भी बाइनरी सर्च एल्गोरिथम समान रहेगा। लेकिन जो तुलना की जाती है वह स्ट्रिंग तुलना पर आधारित होगी। स्ट्रिंग तुलना स्ट्रिंग्स के पहले कैरेक्टर की जांच करें और इसकी तुलना करें। वर्ण समान हैं फिर यह अगले और इसी तरह आगे बढ़ता है।

एल्गोरिदम

arrString : array of sorted strings
Lower = 0 ; upper = n (length of array)
Element = string that is to be found
Step 1 : while element is not found. Do :
Step 2 : mid = lower + (upper - lower) / 2 ;
Step 3 : if arrString[mid] = element , return mid and exit
Step 4 : if arrString[mid] < element, lower = mid+1
Step 5 : if arrString[mid] > element, upper = mid-1
Step 6 : upper < lower , return -1, exit.

उदाहरण

#include<bits/stdc++.h>
using namespace std;
int binarySearchString(string arr[], string x, int n) {
   int lower = 0;
   int upper = n - 1;
   while (lower <= upper) {
      int mid = lower + (upper - lower) / 2;
      int res;
      if (x == (arr[mid]))
         res = 0;
      if (res == 0)
         return mid;
      if (x > (arr[mid]))
         lower = mid + 1;
      else
         upper = mid - 1;
   }
   return -1;
}
int main () {
   string arr[] = {"I", "Love", "Programming" , "tutorials" , "point"};
   string x = "Programming";
   int n = 4;
   int result = binarySearchString(arr, x, n);
   if(result == -1)
      cout<<("Element not present");
   else
      cout<<("Element found at index ")<<result;
}

आउटपुट

Element found at index 2