ในการค้นหาสตริงแบบไบนารี เราได้รับอาร์เรย์ที่เรียงลำดับของสตริง และเราต้องค้นหาสตริงในอาร์เรย์ของสตริงโดยใช้อัลกอริธึมการค้นหาแบบไบนารี
ตัวอย่าง
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
