forked from bamsarts/DS-ALGO
-
Notifications
You must be signed in to change notification settings - Fork 0
/
TernarySearch.cpp
137 lines (120 loc) · 3.48 KB
/
TernarySearch.cpp
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
using namespace std;
/**
* The absolutePrecision can be modified to fit preference but
* it is recommended to not go lower than 10 due to errors that
* may occur.
*/
#define absolutePrecision 10
/**
* The value of _target should be decided or can be decided later
* by using the variable of the function.
*/
#define _target 10
#define MAX 10000000 ///< Maximum length of array
void get_input()
{
}
/**
* This is the iterative method of the ternary search which returns the index of
* the element.
* \param[in] left lower interval limit
* \param[in] right upper interval limit
* \param[in] A array to search in
* \param[in] target value to search for
* \returns index where the target value was found
* \returns -1 if target value not found
*/
int it_ternary_search(int left, int right, int A[], int target)
{
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;
}
}
}
/**
* This is the recursive method of the ternary search which returns the index of
* the element.
* \param[in] left lower interval limit
* \param[in] right upper interval limit
* \param[in] A array to search in
* \param[in] target value to search for
* \returns index where the target value was found
* \returns -1 if target value not found
*/
int rec_ternary_search(int left, int right, int A[], int target)
{
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 is a template function
* You could either use it_ternary_search or rec_ternary_search according to
* preference.
* \param [in] N length of array
* \param[in] A array to search in
* \param[in] target value to search for
*/
void ternary_search(int N, int A[], int target)
{
cout << it_ternary_search(0, N - 1, A, target) << '\t';
cout << rec_ternary_search(0, N - 1, A, target) << '\t';
cout << endl;
}
/** Main function */
int main()
{
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;
}