AN ULTIMATE SEARCHING ALGORITHM

Searching problem fascinates algorithm designers who strive to implement blindingly fast algorithms. Binary search proves to be the best strategy in the worst case. In worst and average case binary search incurs log (n) iterations [1, 2 and 3]. We have come up with a searching algorithm that outperforms binary search by significant margin. Proposed algorithm spends O (1) running time on k < x [0] and k > x[n]. In average case it requires only log (√n) iterations.