chapter21ex7.cpp

// chapter21ex7.cpp : Defines the entry point for the console application.
// Osman Zakir
// 12 / 20 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 21 Exercise 7
// Exercise Specifications:
/**
 * Write a binary search function for a vector<int> (without using the stan-
 * dard one). You can choose any interface you like. Test it. How confident
 * are you that your binary search function is correct? Now write a binary
 * search function for a list<string> . Test it. How much do the two binary
 * search functions resemble each other? How much do you think they
 * would have resembled each other if you had not known about the STL?
 */

#include "../../cust_std_lib_facilities.h"
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>

template<typename Iter, typename Key>
Iter binary_search(Iter first, Iter last, const Key &key);

int main()
{
	std::cout << "Please enter some numbers:\n";
	std::vector<int> vi;
	for (int val; std::cin >> val;)
	{
		std::cin.ignore(32767, '\n');
		vi.push_back(val);
	}
	std::cin.ignore(32767, '\n');
	std::cin.clear();

	std::sort(vi.begin(), vi.end());

	std::cout << "Enter a number to search for: ";
	int key = 0;
	std::cin >> key;
	auto test = ::binary_search(vi.begin(), vi.end(), key);

	if (*test == key)
	{
		std::cout << "Value " << key << " found!\n";
	}
	else
	{
		std::cout << "Sorry, value not found\n";
	}
}

template<typename Iter, typename Key>
Iter binary_search(Iter first, Iter last, const Key &key)
{
	Iter middle = std::next(first, (last - first) / 2);
	if (*middle == key)
	{
		return middle;
	}
	else if (*first == *last)
	{
		return last;
	}
	else if (*first > *last)
	{
		return last;
	}

	if (*middle > key)
	{
		return ::binary_search(first, --middle, key);
	}

	return ::binary_search(++middle, last, key);
}