#algorithm# binary search using loop

binary_search.cpp

#include <algorithm>
#include <ctime>
#include <vector>
#include <iostream>
using namespace std;

// Binary search for a given value in a vector, and return the index of the first found value (-1 for not found).
// The vector should be sorted in ascending order
// Notice:
// 1. Use unsigned int for index type
// 2. Cautious about index overflow
template<class T>
unsigned int _binary_search(const vector<T>& arr, const T& value)
{
    // error handling
    if(arr.size() == 0) return -1;

    // focus on the range is important for this algorithm
    unsigned int low = 0;
    unsigned int high = arr.size() - 1;
    while(low <= high)
    {
        unsigned int index = ((unsigned long long)(low + high)) / 2; // use (unsigned long long) to avoid (low + high) to overflow as unsigned int

        if(arr[index] == value)
        {
            return index;
        }
        else if(arr[index] > value) // value in first half section
        {
            high = index - 1;
        }
        else
        {
            low = index + 1;		// value in second half section
        }
    }

    return -1;
}

// empty array
bool test0()
{
    vector<int> emptyvec;
    int index = _binary_search(emptyvec, 100);
    return index == -1;
}

// array with 1 element
bool test1()
{
    vector<int> onevec;
    int value = 1;
    onevec.push_back(value);
    int index = _binary_search(onevec, value);
    return index == 0;
}

bool compare2search(const vector<int>& vec, int value)
{
    vector<int>::const_iterator it = std::find(vec.begin(), vec.end(), value);
    int index = _binary_search(vec, value);

    if(it == vec.end()) return index == -1; // not exist

    int dist = std::distance(vec.begin(), it);
    return dist  == index;
}

bool test2_help(int v1, int v2)
{
    vector<int> twovec;

    twovec.push_back(v1);
    twovec.push_back(v2);

    std::sort(twovec.begin(), twovec.end());
    if(!compare2search(twovec, v1)) return false;
    if(!compare2search(twovec, v1+v2)) return false; // not exist
    return compare2search(twovec, v2);
}
// array with 2 elements
bool test2()
{
    if(!test2_help(1, 3)) return false; // different value;
    return test2_help(1, 1);			// same value
}

// array with multiple elements
bool test3()
{
    int myints[] = {16,2,77,29, 22, 56, 77, 23, 67, 90, 12, 12, 12, 12, 17873232, 32, 21, 66666, -5, -7, -567};
    vector<int> multiplevec(myints, myints + sizeof(myints) / sizeof(int) );

    std::sort(multiplevec.begin(), multiplevec.end());
    int min = multiplevec[0];
    int max = multiplevec[multiplevec.size()-1];

    if(!compare2search(multiplevec, min)) return false;
    if(!compare2search(multiplevec, max)) return false;
    if(!compare2search(multiplevec, 12)) return false;
    if(!compare2search(multiplevec, 17873232)) return false;
    if(!compare2search(multiplevec, 66666)) return false;
    if(!compare2search(multiplevec, -567)) return false;
    if(!compare2search(multiplevec, -1111111)) return false;
    return compare2search(multiplevec, 77);

}


int main()
{
    typedef bool (*TestFunc)();
    TestFunc tests[] = {test0, test1, test2, test3};
    for(int i = 0; i <= sizeof(tests)/sizeof(tests[0]) - 1; ++i)
    {
        char* status = tests[i]() ? "pass" : "fail";
        cout << "test" << i << ":" << status << endl;
    }
}