Question

How to implement ternary search to find a value in a sorted vector with C++

Answer 1

#include <iostream>
#include <vector>
 
// Ternary search function
int ternarySearch(int l, int r, int key, const std::vector<int>& vec) {
    while (l <= r) {
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;
 
        if (vec[mid1] == key) return mid1;
        if (vec[mid2] == key) return mid2;
 
        if (key < vec[mid1]) {
            r = mid1 - 1;
        } else if (key > vec[mid2]) {
            l = mid2 + 1;
        } else {
            l = mid1 + 1;
            r = mid2 - 1;
        }
    }
     
    return -1; // not found
}
 
int main() {
    std::vector<int> vec = {1, 2, 8, 14, 15, 64, 78, 89, 99, 100, 110, 123};
 
    int tosearch = 89;
 
    int index = ternarySearch(0, vec.size() - 1, tosearch, vec);
 
    if (index != -1)
        std::cout << "Element found at index: " << index << std::endl;
    else
        std::cout << "Element not found.\n";
}
 
 
 
/*
run:
 
Element found at index: 7
 
*/

 

70+ SQL courses for beginners and professionals