/* Uniform binary search algorithm in C
 Source: http://en.wikipedia.org/wiki/Uniform_binary_search
 This code is licensed under the Creative Commons Attribution-ShareAlike License.
 It is from the Wikipedia article "Obfuscated code" dated 2009-02-21. */

/* Uniform binary search is an optimization of the classic binary search
algorithm invented by Donald Knuth and given in Knuth's The Art of
Computer Programming. It uses a lookup table to update a single array
index */


#define LOG_N 42

static int delta[LOG_N];

void make_delta(int N)
{
  int power = 1;
  int i = 0;
  do {
    int half = power;
    power <<= 1;
    delta[i] = (N + half) / power;
  } while (delta[i++] != 0);
}

int unisearch(int *a, int key)
{
  int i = delta[0]-1;  /* midpoint of array */
  int d = 0;

  while (1) {
    if (key == a[i]) return i;
    else if (delta[d] == 0) return -1;
    else {
     if (key < a[i]) i -= delta[++d];
     else i += delta[++d];
    }
  }
}

/* Example of use: */
#define N 10
int main(void)
{
  int i, a[N] = {1,3,5,6,7,9,14,15,17,19};
  make_delta(N);
  for (i=0; i < 20; ++i)
   printf("%d is at index %d\n", i, unisearch(a, i));
  return 0;
}