The code given here and within the analysis is flawed, not that much in the sense that it is not going to work, but in the sense that it follows the idea explained in a wrong way. If the idea was to reach and analyze last about 6 elements, that is not what this code is doing. The bug is subtle. For example this code, which executes if we have an element we want somewhere within first few elements
int mid, i;
mid = i = 2147483647-1;
while (mid > 7)
{
mid = mid / 2;
i -= mid;
}
printf("%d\\n",i);
is giving 34, which means that we will have 34 elements(!) to parse more if the element we are looking for is somewhere at the beginning. This is not even near 7. Only if this code is corrected and tested, we can really compare the idea. To have an algorithm that occasionally parse through 34 elements is really not a binary search even if this is happening here and there. So a very BIG caution about implementing any new idea regarding binary search. Yes, there could be the way and this idea above could be something useful but that must be verified. It seems from this perspective that the flaw of finding first few elements significantly slower is what made this algorithm faster on average. In any case the code above cannot be taken as correct. The gymnastic of pointer and size (here incorrectly named mid) is much more complicated. Known solution with pointers and size with deferred detection looks more like this
int binary_search3s(int a[], int n, int t)
{
int p=0;
while(n>1)
{
if(a\[p + n/2\]<=t)
{
p+=n/2;
n++;
}
n=n/2;
}
if(a\[p\]==t) return p;
return -1;
}
This should be a starting point if anything is to be improved. (3s in the function name is from a family of solutions.)
Aleksandar
