TernarySearch

TernarySearch.cpp

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

class TernarySearch {
private:
    vector<int> data;   // sorted data
    int comparisons;    // count comparisons

    int searchRecursive(int left, int right, int x) {
        if (left <= right) {
            int mid1 = left + (right - left) / 3;
            int mid2 = right - (right - left) / 3;
            comparisons += 2; // two comparisons

            if (data[mid1] == x) return mid1;
            if (data[mid2] == x) return mid2;

            if (x < data[mid1])
                return searchRecursive(left, mid1 - 1, x);
            else if (x > data[mid2])
                return searchRecursive(mid2 + 1, right, x);
            else
                return searchRecursive(mid1 + 1, mid2 - 1, x);
        }
        return -1;
    }

public:

    TernarySearch(const vector<int>& arr) : data(arr), comparisons(0) {}

    // Public interface
    int search(int x) {
        comparisons = 0;
        return searchRecursive(0, data.size() - 1, x);
    }

    int getComparisons() const { return comparisons; }
};


int main() {
    const int N = 1000;
    vector<int> arr(N);
    srand(time(0));

    // Generate sorted array
    for (int i = 0; i < N; ++i)
        arr[i] = i * 2;

    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }

    TernarySearch ts(arr);

    int x;
    cout << "Enter a number to search: ";
    cin >> x;

    int index = ts.search(x);

    if (index != -1)
        cout << "Element found at index: " << index << endl;
    else
        cout << "Element not found." << endl;

    cout << "Comparisons made: " << ts.getComparisons() << endl;
    return 0;
}