在C ++中二进制搜索字符串

  • Z时代
  • 2024-01-10
  • 分类：综合

在二进制搜索字符串中，我们得到了一个排序后的字符串数组，我们必须使用二进制搜索算法在字符串数组中搜索一个字符串。

示例

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

以上是 在C ++中二进制搜索字符串 的全部内容， 来源链接： utcz.com/z/330925.html

回到顶部