binary search.spp

// bindary search : sem 2
//

#include <iostream>
#include <vector>
#include <numeric>


int BinarySearch(const std::vector<int> &values, size_t startIndex, size_t endIndex, const int& value) {
	size_t midIndex = (startIndex + endIndex) / 2;
	while (startIndex < endIndex) {
		if (values.at(midIndex) == value) {
			return midIndex;
		}
		if (values.at(midIndex) > value) {
			endIndex = midIndex;
		} else {
			startIndex = midIndex + 1;
		}
		midIndex = (startIndex + endIndex) / 2;
	}
	return -1;
}

int Search(const std::vector<int> &values, const int& value) {
	size_t startIndex = 0, endIndex = 1;
	if (value < *values.begin() || value > *(values.end() - 1)) {
		return -1;
	}
	while (startIndex < values.size()) {
		if (value < values.at(endIndex)) {
			return BinarySearch(values, startIndex, endIndex, value);
		} else {
			startIndex = endIndex;
			endIndex *= 2;
		}
	}
}

int main() {
	int value;
	std::vector<int> someVec(10); // { 1, 3, 5, 6, 7, 8, 10};
	std::iota(someVec.begin(), someVec.end(), 0);
	std::cin >> value;
	std::cout << Search(someVec, value) << std::endl;
    return 0;
}