Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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.
36 {}

◆ 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]leftlower interval limit
[in]rightupper interval limit
[in]Aarray to search in
[in]targetvalue to search for
Returns
index where the target value was found
-1 if target value not found
48  {
49  while (1) {
50  if (left < right) {
51  if (right - left < absolutePrecision) {
52  for (int i = left; i <= right; i++)
53  if (A[i] == target)
54  return i;
55 
56  return -1;
57  }
58 
59  int oneThird = (left + right) / 3 + 1;
60  int twoThird = (left + right) * 2 / 3 + 1;
61 
62  if (A[oneThird] == target)
63  return oneThird;
64  else if (A[twoThird] == target)
65  return twoThird;
66 
67  else if (target > A[twoThird])
68  left = twoThird + 1;
69  else if (target < A[oneThird])
70  right = oneThird - 1;
71 
72  else
73  left = oneThird + 1, right = twoThird - 1;
74  } else {
75  return -1;
76  }
77  }
78 }

◆ main()

int main ( void  )

Main function

134  {
135  int N = 21;
136  int A[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 10};
137  get_input();
138  ternary_search(N, A, _target);
139  return 0;
140 }
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]leftlower interval limit
[in]rightupper interval limit
[in]Aarray to search in
[in]targetvalue to search for
Returns
index where the target value was found
-1 if target value not found
90  {
91  if (left < right) {
92  if (right - left < absolutePrecision) {
93  for (int i = left; i <= right; i++)
94  if (A[i] == target)
95  return i;
96 
97  return -1;
98  }
99 
100  int oneThird = (left + right) / 3 + 1;
101  int twoThird = (left + right) * 2 / 3 + 1;
102 
103  if (A[oneThird] == target)
104  return oneThird;
105  if (A[twoThird] == target)
106  return twoThird;
107 
108  if (target < A[oneThird])
109  return rec_ternary_search(left, oneThird - 1, A, target);
110  if (target > A[twoThird])
111  return rec_ternary_search(twoThird + 1, right, A, target);
112 
113  return rec_ternary_search(oneThird + 1, twoThird - 1, A, target);
114  } else {
115  return -1;
116  }
117 }

◆ 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]Nlength of array
[in]Aarray to search in
[in]targetvalue to search for
127  {
128  std::cout << it_ternary_search(0, N - 1, A, target) << '\t';
129  std::cout << rec_ternary_search(0, N - 1, A, target) << '\t';
130  std::cout << std::endl;
131 }
Here is the call graph for this function:
ternary_search
void ternary_search(int N, int A[], int target)
Definition: ternary_search.cpp:127
absolutePrecision
#define absolutePrecision
Definition: ternary_search.cpp:22
rec_ternary_search
int rec_ternary_search(int left, int right, int A[], int target)
Definition: ternary_search.cpp:90
std::cout
_target
#define _target
Definition: ternary_search.cpp:27
it_ternary_search
int it_ternary_search(int left, int right, int A[], int target)
Definition: ternary_search.cpp:48
std::endl
T endl(T... args)
std::right
T right(T... args)
get_input
void get_input()
Definition: ternary_search.cpp:36