#include <iostream>
using namespace std;
 
bool binarySearch (int* array, int arraySize, int element)
{
    if ( arraySize == 0 )
    {
        return false;
    }
 
    int startPos = 0;
    int endPos = arraySize;
    while ( true )
    {
        int spanSize = endPos - startPos;
        if ( spanSize == 1 )
        {
            break;
        }
        int pivotPos = startPos + (spanSize >> 1);
        if ( element < array[pivotPos] )
        {
        	// go left
            endPos = pivotPos;
        }
        else
        {
        	// go right
            startPos = pivotPos;
        }
    }
    return element == array[startPos];
}
 
int main()
{
	int array[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	cout << (binarySearch(array, 10, 0) ? "Found." : "Not found.");
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKYm9vbCBiaW5hcnlTZWFyY2ggKGludCogYXJyYXksIGludCBhcnJheVNpemUsIGludCBlbGVtZW50KQp7CiAgICBpZiAoIGFycmF5U2l6ZSA9PSAwICkKICAgIHsKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CgogICAgaW50IHN0YXJ0UG9zID0gMDsKICAgIGludCBlbmRQb3MgPSBhcnJheVNpemU7CiAgICB3aGlsZSAoIHRydWUgKQogICAgewogICAgICAgIGludCBzcGFuU2l6ZSA9IGVuZFBvcyAtIHN0YXJ0UG9zOwogICAgICAgIGlmICggc3BhblNpemUgPT0gMSApCiAgICAgICAgewogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICAgICAgaW50IHBpdm90UG9zID0gc3RhcnRQb3MgKyAoc3BhblNpemUgPj4gMSk7CiAgICAgICAgaWYgKCBlbGVtZW50IDwgYXJyYXlbcGl2b3RQb3NdICkKICAgICAgICB7CiAgICAgICAgCS8vIGdvIGxlZnQKICAgICAgICAgICAgZW5kUG9zID0gcGl2b3RQb3M7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgCS8vIGdvIHJpZ2h0CiAgICAgICAgICAgIHN0YXJ0UG9zID0gcGl2b3RQb3M7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGVsZW1lbnQgPT0gYXJyYXlbc3RhcnRQb3NdOwp9CgppbnQgbWFpbigpCnsKCWludCBhcnJheVsxMF0gPSB7MCwgMSwgMiwgMywgNCwgNSwgNiwgNywgOCwgOX07Cgljb3V0IDw8IChiaW5hcnlTZWFyY2goYXJyYXksIDEwLCAwKSA/ICJGb3VuZC4iIDogIk5vdCBmb3VuZC4iKTsKfQ==