ternary_search.cpp File Reference

Ternary search algorithm More...

#include <iostream>

Include dependency graph for ternary_search.cpp:

Macros
#define	absolutePrecision   10
#define	_target   10
#define	MAX   10000000
	Maximum length of array.

Functions
void	get_input ()
int	it_ternary_search (int left, int right, int A[], int target)
int	rec_ternary_search (int left, int right, int A[], int target)
void	ternary_search (int N, int A[], int target)
int	main ()

Detailed Description

Ternary search algorithm

This is a divide and conquer algorithm. It does this by dividing the search space by 3 parts and using its property (usually monotonic property) to find the desired index.

• Time Complexity : O(log3 n)
• Space Complexity : O(1) (without the array)

Macro Definition Documentation

_target

#define _target   10

The value of _target should be decided or can be decided later by using the variable of the function.

absolutePrecision

#define absolutePrecision   10

The absolutePrecision can be modified to fit preference but it is recommended to not go lower than 10 due to errors that may occur.

Function Documentation

get_input()

void get_input

(

)

get_input function is to receive input from standard IO

Todo:

@christianbender Get input from STDIO or write input to memory as done above.

{}

it_ternary_search()

int it_ternary_search	(	int	left,
		int	right,
		int	A[],
		int	target
	)

This is the iterative method of the ternary search which returns the index of the element.

Parameters

[in]	left	lower interval limit
[in]	right	upper interval limit
[in]	A	array to search in
[in]	target	value to search for

Returns

index where the target value was found

-1 if target value not found

                                                                {
    while (1) {
        if (left < right) {
            if (right - left < absolutePrecision) {
                for (int i = left; i <= right; i++)
                    if (A[i] == target)
                        return i;
 
                return -1;
            }
 
            int oneThird = (left + right) / 3 + 1;
            int twoThird = (left + right) * 2 / 3 + 1;
 
            if (A[oneThird] == target)
                return oneThird;
            else if (A[twoThird] == target)
                return twoThird;
 
            else if (target > A[twoThird])
                left = twoThird + 1;
            else if (target < A[oneThird])
                right = oneThird - 1;
 
            else
                left = oneThird + 1, right = twoThird - 1;
        } else {
            return -1;
        }
    }
}

main()

int main

(

void

)

Main function

           {
    int N = 21;
    int A[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 10};
    get_input();
    ternary_search(N, A, _target);
    return 0;
}

Here is the call graph for this function:

rec_ternary_search()

int rec_ternary_search	(	int	left,
		int	right,
		int	A[],
		int	target
	)

This is the recursive method of the ternary search which returns the index of the element.

Parameters

[in]	left	lower interval limit
[in]	right	upper interval limit
[in]	A	array to search in
[in]	target	value to search for

Returns

index where the target value was found

-1 if target value not found

                                                                 {
    if (left < right) {
        if (right - left < absolutePrecision) {
            for (int i = left; i <= right; i++)
                if (A[i] == target)
                    return i;
 
            return -1;
        }
 
        int oneThird = (left + right) / 3 + 1;
        int twoThird = (left + right) * 2 / 3 + 1;
 
        if (A[oneThird] == target)
            return oneThird;
        if (A[twoThird] == target)
            return twoThird;
 
        if (target < A[oneThird])
            return rec_ternary_search(left, oneThird - 1, A, target);
        if (target > A[twoThird])
            return rec_ternary_search(twoThird + 1, right, A, target);
 
        return rec_ternary_search(oneThird + 1, twoThird - 1, A, target);
    } else {
        return -1;
    }
}

Here is the call graph for this function:

ternary_search()

void ternary_search	(	int	N,
		int	A[],
		int	target
	)

ternary_search is a template function You could either use it_ternary_search or rec_ternary_search according to preference.

Parameters

[in]	N	length of array
[in]	A	array to search in
[in]	target	value to search for

                                                {
    std::cout << it_ternary_search(0, N - 1, A, target) << '\t';
    std::cout << rec_ternary_search(0, N - 1, A, target) << '\t';
    std::cout << std::endl;
}

Here is the call graph for this function: