Can this algorithm still be considered a Binary Search algorithm?

Problem Detail: 

While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as follows:

If i have a sorted array of lenght 100 and I see its starting field contains the number 200 and its ending field contains the number 400, me, as a maths studying human, would be likely to start searching around field 35 if I was searching the number 270, and not the field 50 like in a normal binary search algorithm.

Then, if the number on field 35 of the array is 270, 35 is the index I was searching for.

If that isn't the case I can compare the number I got (say 280) and repeat the operation taking the lower part of the array (so I have 35 fields with the starting field containing 200 and the ending field containing 280) if the number I found is greater than what I'm searching for, or the upper part of the array (say I got 260: now I have 65 indexes, the first one containing 260 and the final one containing 400. Orientatively, I would head torward index 4 of this sub array, which is index 39 of the entire array) if the number I got is smaller than the number I'm searching for.

The question is: can this algorithm be considered a binary search algorithm? If not, has it got its own name?

Asked By : user6245072

Answered By : Taemyr

I would not call this a binary search.

It is clearly similar to binary search and it's natural to see it as a refinement of binary search. However it has significantly different algorithm complexity characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n) worst case run time.

I prefer to say "The worst case run time of binary search is O(log(n))" rather than "Depending on the choice of bounding elements the worst case run time of binary search is O(log(n))". This means that I can not classify Interpolation search as a binary search algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59720