Trong Tìm kiếm nhị phân một chuỗi, chúng ta được cung cấp một mảng các chuỗi đã được sắp xếp và chúng ta phải tìm kiếm một chuỗi trong mảng chuỗi bằng cách sử dụng thuật toán tìm kiếm nhị phân.
Ví dụ
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’ Tìm kiếm nhị phân là kỹ thuật tìm kiếm hoạt động bằng cách tìm giữa mảng để tìm phần tử.
Đối với mảng các chuỗi, thuật toán tìm kiếm nhị phân sẽ vẫn như cũ. Nhưng so sánh được thực hiện sẽ dựa trên so sánh chuỗi. So sánh chuỗi kiểm tra ký tự đầu tiên của các chuỗi và so sánh nó. các ký tự giống nhau sau đó chuyển sang ký tự tiếp theo và cứ tiếp tục như vậy.
Thuật toán
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.
Ví dụ
#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;
} Đầu ra
Element found at index 2