ternary_search.cpp File Reference

Ternary search algorithm More...

#include <iostream>

Include dependency graph for ternary_search.cpp:

Go to the source code of this file.

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)

Definition in file ternary_search.cpp.

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.

Definition at line 27 of file ternary_search.cpp.

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.

Definition at line 22 of file ternary_search.cpp.

MAX

#define MAX   10000000

Maximum length of array.

Definition at line 29 of file ternary_search.cpp.

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.

Definition at line 36 of file ternary_search.cpp.

{}

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

Definition at line 48 of file ternary_search.cpp.

                                                                {
    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

Definition at line 134 of file ternary_search.cpp.

           {
    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;
}

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

Definition at line 90 of file ternary_search.cpp.

                                                                 {
    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;
    }
}

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

Definition at line 127 of file ternary_search.cpp.

                                                {
    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;
}