โปรแกรม C++ Binary Search สำหรับค้นหาลำดับข้อมูล (Search Sequence)

ภาพรวม

โปรแกรม C++ นี้สาธิตการใช้ Binary Search เพื่อหาตำแหน่งเริ่มต้นของลำดับข้อมูล (Search Sequence) ในอาร์เรย์ที่เรียงลำดับ แล้วตรวจสอบว่าลำดับต่อเนื่องตรงกันหรือไม่ ความซับซ้อนด้านเวลา O(log n + m) โดย m คือความยาวลำดับที่ค้นหา

ขั้นตอนและ Pseudocode

1. ฟังก์ชัน BinarySearch() ค้นหาตัวแรกของลำดับ (b[0]) ในอาร์เรย์หลัก
2. คำนวณ mid = start + (end - start + 1) / 2
3. เปรียบเทียบและตัดครึ่งพื้นที่ค้นหาตามปกติ
4. คืนค่าดัชนีที่พบ (หรือ -1 ถ้าไม่พบ)
5. ใน main(): ตรวจสอบว่าองค์ประกอบต่อจากดัชนีที่พบ ตรงกับลำดับที่เหลือของ b[] หรือไม่

โค้ดตัวอย่าง (แก้ไขให้ทำงานได้)

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector& arr, int start, int end, int item) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (item == arr[mid]) return mid;
        else if (item < arr[mid]) end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

int main() {
    vector arr = {1, 7, 15, 26, 29, 35, 38, 40, 49, 51};
    int len = arr.size();
    
    int seqLen;
    cout << "Enter the number of elements in the search sequence: ";
    cin >> seqLen;
    
    vector seq(seqLen);
    for (int i = 0; i < seqLen; i++) {
        cin >> seq[i];
    }
    
    int foundIdx = binarySearch(arr, 0, len - 1, seq[0]);
    
    if (foundIdx == -1) {
        cout << "\nNot found.";
    } else {
        bool match = true;
        for (int i = 0; i < seqLen; i++) {
            if (foundIdx + i >= len || arr[foundIdx + i] != seq[i]) {
                match = false;
                break;
            }
        }
        
        if (match) {
            cout << "\nSequence found between index " << foundIdx << " and " << foundIdx + seqLen - 1 << ".";
        } else {
            cout << "\nNot found.";
        }
    }
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the number of elements in the search sequence: 4
15 26 29 35
Sequence found between index 2 and 5.

การประยุกต์ใช้

• การค้นหา substring/pattern ในข้อมูลที่เรียงลำดับ
• การตรวจสอบลำดับ DNA, time series data, log sequences
• สามารถขยายเป็นการค้นหาแบบ fuzzy/approximate ได้