โปรแกรม C++ เปรียบเทียบ Binary Search และ Linear Search

ภาพรวม

โปรแกรม C++ นี้เปรียบเทียบประสิทธิภาพระหว่าง Binary Search (O(log n)) และ Linear Search (O(n)) โดยนับจำนวนรอบการวนลูป (Iterations) ในการค้นหาแต่ละครั้ง แสดงให้เห็นว่า Binary Search ดีกว่าในกรณีทั่วไป แต่ Linear Search อาจดีกว่าเมื่อข้อมูลอยู่หน้าสุด

อัลกอริธึม

Binary Search

1. ฟังก์ชัน BinarySearch(arr, start, end, item, iter)
2. เพิ่มตัวนับ iteration, คำนวณ mid
3. เปรียบเทียบ item กับ arr[mid] ตัดครึ่งพื้นที่ค้นหา
4. คืนค่าจำนวน iteration เมื่อพบหรือไม่พบ

Linear Search

1. ฟังก์ชัน LinearSearch(arr, n, item)
2. วนลูป i = 0 ถึง n-1 เพิ่ม iteration ทุกรอบ
3. ถ้าเจอ คืนค่า iteration, ไม่เจอก็คืนค่า n

โค้ดตัวอย่าง (แก้ไข hardcoded array size)

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

int binarySearch(const vector& arr, int start, int end, int item, int& iterations) {
    iterations = 0;
    while (start <= end) {
        iterations++;
        int mid = start + (end - start) / 2;
        cout << "\nIteration " << iterations;
        
        if (item == arr[mid]) {
            cout << "\nItem found at " << mid << " index.";
            return iterations;
        } else if (item < arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    cout << "\nNot found";
    return iterations;
}

int linearSearch(const vector& arr, int item, int& iterations) {
    iterations = 0;
    for (size_t i = 0; i < arr.size(); i++) {
        iterations++;
        cout << "\nIteration " << iterations;
        if (arr[i] == item) {
            cout << "\nItem found at " << i << " index.";
            return iterations;
        }
    }
    cout << "\nNot found";
    return iterations;
}

int main() {
    vector arr = {2, 7, 14, 24, 26, 35, 38, 41, 49, 53};
    
    char choice;
    do {
        int item;
        cout << "\nEnter the element to be searched: ";
        cin >> item;
        
        int bIter, lIter;
        cout << "\n\n\t\t\tBinary Search:";
        int bResult = binarySearch(arr, 0, arr.size()-1, item, bIter);
        
        cout << "\n\n\t\t\tLinear Search:";
        int lResult = linearSearch(arr, item, lIter);
        
        cout << "\n\n";
        if (lIter > bIter) {
            cout << "Binary search is better for this search.";
        } else if (lIter < bIter) {
            cout << "Linear search is better for this search.";
        } else {
            cout << "Both are equally efficient for this search.";
        }
        
        cout << "\n\nDo you want to search more...enter choice(y/n)? ";
        cin >> choice;
    } while (choice == 'y' || choice == 'Y');
    
    return 0;
}

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

Enter the element to be searched: 7
Binary Search: Iteration 1 Iteration 2 Iteration 3 Iteration 4 Item found at 1 index.
Linear Search: Iteration 1 Iteration 2 Item found at 1 index.
Linear search is better for this search.

Enter the element to be searched: 53
Binary Search: Iteration 1 Item found at 9 index.
Linear Search: Iteration 1 Iteration 2 ... Iteration 10 Item found at 9 index.
Binary search is better for this search.

สรุปการเปรียบเทียบ