1//! @file search.hpp
2//! @author ryftchen
3//! @brief The declarations (search) in the algorithm module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <cmath>
10#include <cstdint>
11#include <numeric>
12#include <vector>
13
14//! @brief The algorithm module.
15namespace algorithm // NOLINT(modernize-concat-nested-namespaces)
16{
17//! @brief Search-related functions in the algorithm module.
18namespace search
19{
20//! @brief Brief function description.
21//! @return function description (module_function)
22inline static const char* description() noexcept
23{
24 return "ALGO_SEARCH";
25}
26extern const char* version() noexcept;
27
28//! @brief Search methods.
29//! @tparam Elem - type of element
30template <typename Elem>
31class Search
32{
33public:
34 //! @brief Binary.
35 //! @param array - ordered array to be searched
36 //! @param length - length of array
37 //! @param key - search key
38 //! @return index of the first occurrence of key
39 static std::int64_t binary(const Elem* const array, const std::uint32_t length, const Elem key);
40 //! @brief Interpolation.
41 //! @param array - ordered array to be searched
42 //! @param length - length of array
43 //! @param key - search key
44 //! @return index of the first occurrence of key
45 static std::int64_t interpolation(const Elem* const array, const std::uint32_t length, const Elem key);
46 //! @brief Fibonacci.
47 //! @param array - ordered array to be searched
48 //! @param length - length of array
49 //! @param key - search key
50 //! @return index of the first occurrence of key
51 static std::int64_t fibonacci(const Elem* const array, const std::uint32_t length, const Elem key);
52
53private:
54 //! @brief Generate Fibonacci number.
55 //! @param limit - smallest integer that is not greater than the maximum value of the Fibonacci sequence
56 //! @return Fibonacci sequence
57 static std::vector<std::uint32_t> generateFibonacciNumber(const std::uint32_t limit);
58};
59
60template <typename Elem>
61std::int64_t Search<Elem>::binary(const Elem* const array, const std::uint32_t length, const Elem key)
62{
63 if (!array || (length == 0))
64 {
65 return -1;
66 }
67
68 std::uint32_t lower = 0;
69 std::uint32_t upper = length - 1;
70 if ((key < array[lower]) || (key > array[upper]))
71 {
72 return -1;
73 }
74
75 std::int64_t index = -1;
76 while (lower <= upper)
77 {
78 const std::uint32_t mid = std::midpoint(a: lower, b: upper);
79 if (key == array[mid])
80 {
81 index = mid;
82 break;
83 }
84 if (key > array[mid])
85 {
86 lower = mid + 1;
87 }
88 else
89 {
90 upper = mid - 1;
91 }
92 }
93 return index;
94}
95
96template <typename Elem>
97std::int64_t Search<Elem>::interpolation(const Elem* const array, const std::uint32_t length, const Elem key)
98{
99 if (!array || (length == 0))
100 {
101 return -1;
102 }
103
104 std::uint32_t lower = 0;
105 std::uint32_t upper = length - 1;
106 if ((key < array[lower]) || (key > array[upper]))
107 {
108 return -1;
109 }
110
111 std::int64_t index = -1;
112 while (lower <= upper)
113 {
114 if (array[upper] == array[lower])
115 {
116 index = (key == array[lower]) ? lower : -1;
117 break;
118 }
119
120 const std::uint32_t mid = lower + ((upper - lower) * (key - array[lower]) / (array[upper] - array[lower]));
121 if (key == array[mid])
122 {
123 index = mid;
124 break;
125 }
126 if (key > array[mid])
127 {
128 lower = mid + 1;
129 }
130 else
131 {
132 upper = mid - 1;
133 }
134 }
135 return index;
136}
137
138template <typename Elem>
139std::int64_t Search<Elem>::fibonacci(const Elem* const array, const std::uint32_t length, const Elem key)
140{
141 if (!array || (length == 0))
142 {
143 return -1;
144 }
145
146 std::uint32_t lower = 0;
147 std::uint32_t upper = length - 1;
148 if ((key < array[lower]) || (key > array[upper]))
149 {
150 return -1;
151 }
152 const auto fib = generateFibonacciNumber(limit: length);
153 if (constexpr std::uint8_t minSize = 3; fib.size() < minSize)
154 {
155 return -1;
156 }
157
158 std::uint32_t n = fib.size() - 1;
159 const std::uint32_t paddedSize = fib[n] - 1;
160 std::vector<Elem> complement(paddedSize);
161 std::copy(array, array + length, complement.begin());
162 for (std::uint32_t i = length; i < paddedSize; ++i)
163 {
164 complement[i] = array[upper];
165 }
166
167 std::int64_t index = -1;
168 while ((lower <= upper) && (n >= 2))
169 {
170 std::uint32_t mid = lower + fib[n - 1] - 1;
171 if (mid >= paddedSize)
172 {
173 mid = paddedSize - 1;
174 }
175
176 if (complement[mid] > key)
177 {
178 if (mid == 0)
179 {
180 break;
181 }
182 upper = mid - 1;
183 --n;
184 }
185 else if (complement[mid] < key)
186 {
187 lower = mid + 1;
188 n -= 2;
189 }
190 else
191 {
192 index = (mid <= upper) ? mid : upper;
193 break;
194 }
195 }
196 return index;
197}
198
199template <typename Elem>
200std::vector<std::uint32_t> Search<Elem>::generateFibonacciNumber(const std::uint32_t limit)
201{
202 if (limit == 0)
203 {
204 return {};
205 }
206
207 const double estimate = std::log(x: limit * std::sqrt(x: 5.0)) / std::log(x: std::numbers::phi);
208 std::vector<std::uint32_t> fibonacci{};
209 fibonacci.reserve(n: static_cast<std::size_t>(std::ceil(x: estimate)));
210 for (std::uint32_t f1 = 0, f2 = 1;;)
211 {
212 const std::uint32_t temp = f1 + f2;
213 f1 = f2;
214 f2 = temp;
215 fibonacci.emplace_back(args&: f1);
216
217 if (f1 > limit)
218 {
219 break;
220 }
221 }
222 return fibonacci;
223}
224} // namespace search
225} // namespace algorithm
226