Binary search on a list with no fixed size

Question

There is a reliable algorithm capable of performing a binary search on a list where one cannot consider the size (length or count) of the list?

I know that one of the requirements for a binary search is to know this size to divide the list, but in my case, I do not have this list loaded in memory, it will be available in an external medium that will only receive the index of the item as parameter, returning the value contained in the index.

Answer 1

I’ll assume you’re using some form of array and have access to it, even if this is just the internal representation. Otherwise I don’t see how to do even a simple search.

This may depend somewhat on the language you are using. The language needs to have a way to find out whether an index is valid or not. The problem is, as far as I know, whenever you don’t know the amount of items, you also don’t know when the index is invalid. Then I’d say it’s impossible.

If you get this information, you can look at each item by doubling the index if what you’re looking for is higher than the value found in that index and see if it’s still valid or not (capturing an exception or other way that the language allows). If what you are looking for is less than the value of the item found, then you take half of the current item and the last checked and no longer need to worry about checking if the item is valid. If you have already found a smaller one, then when you have to look at a larger one you should consider the half between this item and the largest previously found.

Another way is to find the size before doing just binary search. You can use the same technique or do the classic binary search considering that the imaginary size would be 2 to 32. It’s the reverse process, every time you make a mistake, you divide the index by 2, every time you don’t make a mistake, you take half. When there is no error try the half between the one that did not give error and the last one. With the size you do traditional binary search.

Honestly, although I can’t prove it, I think this is a false problem precisely because of the requirement to know when the index is going to pop. In a data/language structure (any array or guys who use array in its implementation in Java, C#, etc.) which can indicate if you have exceeded the limit, the size is available and just ask. In C, if the programmer has how to know the size when mounting a array or another structure based on it. What can happen is the code deliberately ignores the size. Why do this? If you do, I find it impossible to solve. In C, if you throw away the size of the array, you won’t know if you’ve accessed a place you shouldn’t.

Of course there may be specific ways to get this if the value has a pattern that is guaranteed not to be confused with something else and see if it is still in the area of array. Even that, I believe that we can not guarantee this.

Other than that, demonstrate the real need. Show how to do the simple search in this case to see if we can turn into binary search.