// Binary search in the array with the statically known bounds
// http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary

#include <stdio.h>
#include <assert.h>

class index
{
    int v;
    index();
    index(int i): v(i) {}

public:
    index(const index &i): v(i.v) {}
    int as_int() const {return v;}

    static const int MIN = 0;
    static const int MAX = 255;
    static const index min() {return index(MIN);}
    static const index max() {return index(MAX);}

    // bounded increment: not past h
    bool incr(const index h)
    { 
	if(v >= h.v)
	    return false;
	v++;
	return true;
    }

    // bounded decrement: not past l
    bool decr(const index l)
    { 
	if(v <= l.v)
	    return false;
	v--;
	return true;
    }

    // average two indices
    index middle(const index other) const
    {
	return index(v + (other.v-v)/2);
    }
};

class fixed_array
{
    int array[index::MAX - index::MIN + 1];

public:
    fixed_array() 
    { 
	assert(sizeof(array) > 0);
	for(int i=0; i<sizeof(array)/sizeof(array[0]); i++)
	  array[i] = 10*i+1;
    }

    int operator [] (const index i) const { return array[i.as_int() - index::MIN]; }
    int& operator [] (const index i) { return array[i.as_int() - index::MIN]; }
};

int search(const fixed_array &array, const int target) {
    index low = index::min(), high = index::max();
    for (;;) {
	index mid = low.middle(high);
	const int v = array[mid];
	if (v == target) return mid.as_int();
	if (v < target)
	    if (mid.incr(high)) low  = mid; else return -1;
	else
	    if (mid.decr(low )) high = mid; else return -1;
    }
}

void test(const int target)
{
  fixed_array fixedarray;
  printf("\ntesting, target %d, found index %d\n", target, search(fixedarray, target));
}

int main(void)
{
  test(-1);
  test(1);
  test(10);
  test(11);
  test(1280);
  test(1281);
  test(2550);
  test(2551);
  test(2552);
  return 0;
}