diff options
Diffstat (limited to '01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search')
3 files changed, 39 insertions, 0 deletions
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp new file mode 100644 index 0000000..c93e2cf --- /dev/null +++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp @@ -0,0 +1,36 @@ +#include <iostream> +#include <cassert> +#include <vector> + +using std::vector; + +int binary_search(const vector<int> &a, int x) { + int left = 0, right = (int)a.size(); + //write your code here +} + +int linear_search(const vector<int> &a, int x) { + for (size_t i = 0; i < a.size(); ++i) { + if (a[i] == x) return i; + } + return -1; +} + +int main() { + int n; + std::cin >> n; + vector<int> a(n); + for (size_t i = 0; i < a.size(); i++) { + std::cin >> a[i]; + } + int m; + std::cin >> m; + vector<int> b(m); + for (int i = 0; i < m; ++i) { + std::cin >> b[i]; + } + for (int i = 0; i < m; ++i) { + //replace with the call to binary_search when implemented + std::cout << linear_search(a, b[i]) << ' '; + } +} diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01 b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01 new file mode 100644 index 0000000..94106f5 --- /dev/null +++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01 @@ -0,0 +1,2 @@ +5 1 5 8 12 13 +5 8 1 23 1 11 diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01.a b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01.a new file mode 100644 index 0000000..b1857aa --- /dev/null +++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01.a @@ -0,0 +1 @@ +2 0 -1 0 -1 |