Tìm kiếm nhị phân chuỗi trong C++

Trong tìm kiếm nhị phân chuỗi, cho mảng chuỗi đã sắp xếp, cần tìm một chuỗi trong mảng bằng thuật toán tìm kiếm nhị phân.

Ví dụ

Input: stringArray = {"I", "Love", "Programming", "tutorials", "point"}. Element = "programming" Output: chuỗi tìm thấy tại chỉ số 3
Giải thích: Chỉ số của chuỗi là 3.
Input: stringArray = {"I", "Love", "Programming", "tutorials", "point"}. Element = "coding" Output: -1 'chuỗi không tìm thấy'

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 chuỗi, thuật toán tìm kiếm nhị phân giữ nguyên. Nhưng các so sánh 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ếu ký tự giống nhau thì chuyển sang ký tự tiếp theo, và cứ thế.

Thuật toán

arrString: mảng chuỗi đã sắp xếp
Lower = 0; upper = n (độ dài mảng)
Element = chuỗi cần tìm
Bước 1: while element chưa tìm thấy. Làm:
Bước 2: mid = lower + (upper - lower) / 2;
Bước 3: if arrString[mid] = element, return mid và thoát
Bước 4: if arrString[mid] < element, lower = mid+1
Bước 5: if arrString[mid] > element, upper = mid-1
Bước 6: upper < lower, return -1, thoát.

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<<("Phần tử không có");
    else cout<<("Phần tử tìm thấy tại chỉ số ")<<result;
}

Kết quả

Phần tử tìm thấy tại chỉ số 2