Published by
Sep 24, 2013 (last update: Sep 25, 2013)

Ternary search.

Score: 3.1/5 (105 votes)
*****
So, after much trying, I finally managed to implement a ternary search in recursivity mode!

The ternary search follows the same idea of binary search, but splitting the vector into 3 parts, two index: One for left and one to the right and a third search in the middle!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
using namespace std;

#define s 12 //I gave space in the array as 12,but you can give the number you want.

int ternary_search (int v[],int n, int left, int right, int x);
int main()
{
    int v[s];
    short x;
    for(int i = 1; i <= s; i++)
    {
        v[i-1] = i;
    }
    cout << "Enter number for research:\n";
    cin >> x;

    int left = s/3;
    int right = (s/3)*2;

    if(ternary_search(v,s,left-1,right-1,x) == -1)
    {
        cout<<"Number does not exist in array.\n";
    }
    else
    {
        cout<<"The index is:"<<ternary_search(v,s,left-1,right-1,x)<<"\n";
    }
    return 0;
}
int ternary_search (int v[],int n, int left, int right, int x)
{

    if(left < 0 || right > n-1 || left > right)
    {
        return -1;
    }
    if(x == v[left])
    {
        return left;
    }

    if(x == v[right])
    {
        return right;
    }

   // Update the two index left and right if the element is not found.


    if(x < v[left])
    {
        return ternary_search(v,n,left-1,right,x);
    }

    if (x > v[left] && x < v[right])
    {

        return ternary_search(v,n,left+1,right-1,x);
    }

    if(x > v[right])
    {
        return ternary_search(v,n,left,right+1,x);
    }
}