Search Recursive-TERNARY SEARCH

This is ternary search algorithm.This algorithm is almost similar to the binary search algorithm.

Here the array is divided into three and we will have two mid elements.
                                         1. MID_FIRST
                                         2.MID_SECOND

FIRST ARRAY:  FROM STARTING INDEX TO ELEMENT BEFORE MID_FIRST

SECOND ARRAY:  FROM ELEMENT NEXT TO MID_SECOND TO THE END

THIRD ARRAY:  FROM MID_FIRST TO MID_SECOND

From these arrays we search recursively to find the key.

Source code:

       

///source code to implement ternary search...



#include<iostream>

using namespace std;



int ternary_search(int *a,int starting,int ending,int key){

    if(starting<ending){



        ///THIS IS THE FIRST MID

        int mid_first=starting+(ending-starting)/3;



        ///THIS IS THE SECOND MID

        int mid_second=mid_first+(ending-starting)/3;



        if(a[mid_first]==key){

            return 1;

        }



        if(a[mid_second]==key){

            return 1;

        }



        ///FIRST ARRAY FROM STARTING INDEX TO ELEMENT BEFORE MID_FIRST

        if(key<a[mid_first]){

            return ternary_search(a,starting,mid_first,key);

        }



        ///SECOND ARRAY FROM ELEMENT NEXT TO MID_SECOND TO THE END

        else if(key>a[mid_second]){

            return ternary_search(a,mid_second+1,ending,key);

        }



        ///THIRD ARRAY FROM MID_FIRST TO MID_SECOND

        return ternary_search(a,mid_first,mid_second+1,key);

    }



    return 0;

}

int main()

{

    int *a,n,no;



    cout<<"enter no of elements in an array";

    cin>>n;

    a=new int[n];



    ///getting array elements

    ///important condition :: the array should be in sorted order to perform binary search..

    for(int i=0;i<n;i++){

        cin>>a[i];

    }



    cout<<"enter the element to be searched";

    cin>>no;



    ///calling ternary search function

    ///here the array is divided into three with two mid value

    if(ternary_search(a,0,n,no)){

        cout<<"FOUND\n";

    }

    else{

        cout<<"NOT FOUND\n";

    }



    return 0;

}