C++에서 문자열 이진 검색

이진 검색 문자열에서는 정렬된 문자열 배열이 제공되며 이진 검색 알고리즘을 사용하여 문자열 배열에서 문자열을 검색해야 합니다.

예시

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