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-2025 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; static_cast<std::int32_t>(fib.size() - 1) < minSize)
154 {
155 return -1;
156 }
157
158 std::uint32_t n = fib.size() - 1;
159 std::vector<Elem> complement(array, array + (fib[n] - 1));
160 for (std::uint32_t i = upper; i < (fib[n] - 1); ++i)
161 {
162 complement[i] = array[upper];
163 }
164
165 std::int64_t index = -1;
166 while ((lower <= upper) && (n >= 1))
167 {
168 const std::uint32_t mid = lower + fib[n - 1] - 1;
169 if (complement[mid] > key)
170 {
171 upper = mid - 1;
172 --n;
173 }
174 else if (complement[mid] < key)
175 {
176 lower = mid + 1;
177 n -= 2;
178 }
179 else
180 {
181 if (mid <= upper)
182 {
183 index = mid;
184 break;
185 }
186
187 index = upper;
188 break;
189 }
190 }
191 return index;
192}
193
194template <typename Elem>
195std::vector<std::uint32_t> Search<Elem>::generateFibonacciNumber(const std::uint32_t limit)
196{
197 if (limit == 0)
198 {
199 return {};
200 }
201
202 const double estimate = std::log(x: limit * std::sqrt(x: 5.0)) / std::log(x: std::numbers::phi);
203 std::vector<std::uint32_t> fibonacci{};
204 fibonacci.reserve(n: static_cast<std::size_t>(std::ceil(x: estimate)));
205 for (std::uint32_t f1 = 0, f2 = 1;;)
206 {
207 const std::uint32_t temp = f1 + f2;
208 f1 = f2;
209 f2 = temp;
210 fibonacci.emplace_back(args&: f1);
211
212 if (f1 > limit)
213 {
214 break;
215 }
216 }
217 return fibonacci;
218}
219} // namespace search
220} // namespace algorithm
221