diff options
author | Aryadev Chavali <aryadev@aryadevchavali.com> | 2024-04-29 15:43:17 +0530 |
---|---|---|
committer | Aryadev Chavali <aryadev@aryadevchavali.com> | 2024-04-29 15:43:17 +0530 |
commit | 4359caa3ca15c75c4241d869259af3be8cc8375f (patch) | |
tree | 7ccb8c1dc8f8846adddf6e67d4912cf6f4aaab62 /impls/bsearch.cpp | |
parent | d30043274d010e3246946166a5d7e81cb583038a (diff) | |
download | algorithms-4359caa3ca15c75c4241d869259af3be8cc8375f.tar.gz algorithms-4359caa3ca15c75c4241d869259af3be8cc8375f.tar.bz2 algorithms-4359caa3ca15c75c4241d869259af3be8cc8375f.zip |
Moved implementations to folder
Diffstat (limited to 'impls/bsearch.cpp')
-rw-r--r-- | impls/bsearch.cpp | 57 |
1 files changed, 57 insertions, 0 deletions
diff --git a/impls/bsearch.cpp b/impls/bsearch.cpp new file mode 100644 index 0000000..6172b15 --- /dev/null +++ b/impls/bsearch.cpp @@ -0,0 +1,57 @@ +/* bsearch.cpp + * Created: 2023-07-10 + * Author: Aryadev Chavali + */ + +#include <algorithm> +#include <cstdlib> +#include <fstream> +#include <iostream> +#include <string> +#include <vector> + +using std::cin; +using std::cout; +using std::endl; +using std::ostream; +using std::string; +using std::vector; + +vector<int> arr; + +ostream &print_arr(ostream &os) +{ + os << "["; + for (size_t i = 0; i < arr.size(); ++i) + os << arr[i] << (i == arr.size() - 1 ? "" : ","); + return os << "]"; +} + +int bsearch(int n, int l = 0, int u = arr.size() - 1) +{ + int midpoint = ((u + l) / 2); + if (l >= u || u <= 0) + return -1; + int val = arr[midpoint]; + if (val == n) + return midpoint; + else if (val > n) + return bsearch(n, l, midpoint - 1); + else + return bsearch(n, midpoint + 1, u); +} + +int main(void) +{ + std::ifstream input("bsearch.txt"); + string line; + while (std::getline(input, line)) + arr.push_back(std::stoi(line)); + std::sort(std::begin(arr), std::end(arr)); + string inp; + cout << "Enter number to search: "; + cin >> inp; + int to_search = std::stoi(inp); + cout << bsearch(to_search) << endl; + return 0; +} |