/* 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; }
Hide code	Visustin flow chart for C/C++