ternary search Algorithm
The ternary search algorithm is an advanced searching technique that aims to find the minimum or maximum value of a unimodal function or determine the position of a specific target value within a sorted array. The algorithm is based on the divide and conquer strategy, where it divides the search interval into three equal parts and subsequently evaluates the function at two intermediate points. By comparing the function values at these points, the algorithm narrows down the search interval to one of the three sub-intervals, which contains the desired minimum or maximum value.
The efficiency of the ternary search algorithm lies in its ability to discard a significant portion of the search interval with each iteration, thereby reducing the number of comparisons required to locate the target value. This results in a logarithmic time complexity of O(log3 N), where N represents the size of the search interval. Although the ternary search algorithm performs fewer iterations compared to the binary search algorithm, it requires evaluating the function at two points, which can make it less efficient than binary search in certain scenarios. Nevertheless, the ternary search algorithm is an effective approach for solving optimization problems and searching through large datasets with a unimodal structure.
// Ternary Search implemented in C++
//
// Binary search works for a sorted array.
// More documentation about the algorithm
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/cpp/category/algorithm
// https://github.com/allalgorithms/cpp
//
// Contributed by: Sriram Desai
// Github: @desai10
//
#include <iostream>
#include <vector>
using namespace std;
vector<int> ar;
int ternary_search(int l,int r, int x)
{
if(r>=l)
{
int mid1 = l + (r-l)/3;
int mid2 = r - (r-l)/3;
if(ar[mid1] == x)
return mid1;
if(ar[mid2] == x)
return mid2;
if(x<ar[mid1])
return ternary_search(l,mid1-1,x);
else if(x>ar[mid2])
return ternary_search(mid2+1,r,x);
else
return ternary_search(mid1+1,mid2-1,x);
}
return -1;
}
int main(int argc, char const *argv[])
{
int n, key;
cout << "Enter size of array: ";
cin >> n;
cout << "Enter array elements: ";
for (int i = 0; i < n; ++i)
{
int t;
cin>>t;
ar.push_back(t);
}
cout << "Enter search key: ";
cin>>key;
int res = ternary_search(0, n-1, key);
if(res != -1)
cout<< key << " found at index " << res << endl;
else
cout << key << " not found" << endl;
return 0;
}