ในการค้นหาแบบทวิภาคสำหรับสตริง เราได้รับอาร์เรย์ของสตริงที่เรียงลำดับแล้ว และเราต้องค้นหาสตริงในอาร์เรย์ของสตริงโดยใช้อัลกอริทึมค้นหาแบบทวิภาค
ตัวอย่าง
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'Binary search เป็นเทคนิคการค้นหาที่ทำงานโดยการหาจุดกลางของอาร์เรย์เพื่อหาสมาชิก
สำหรับอาร์เรย์ของสตริง อัลกอริทึมค้นหาแบบทวิภาคจะเหมือนเดิม แต่การเปรียบเทียบจะเป็นการเปรียบเทียบสตริง String comparison ตรวจสอบตัวอักษรแรกของสตริงและเปรียบเทียบ ถ้าตัวอักษรเหมือนกัน จะไปต่อที่ตัวถัดไป และต่อไปเรื่อยๆ
อัลกอริทึม
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
