Is there a reliable algorithm that can perform a binary search in a list where the size ( length or count ) of the list can not be considered?
I know one of the requirements for a binary search is to know this size to split the list, but in my case, I do not have this list loaded into memory, it will be available in an external medium that will only receive the index of the item as a parameter , returning the value contained in the index.
I'll assume you're using some form of array and have access to it, even if it's just the inner representation. Otherwise I do not see how to do even a simple search.
This may depend somewhat on the language you are using. Language must be able to find out if an index is valid or not. The problem is that as far as I know, whenever you do not know the amount of items, you also do not know when the index is invalid. So I would say it's impossible.
If you get this information, you can go looking at each item by folding the index if what you are looking for is larger than the value found in that index and seeing if it is still valid or not (capturing an exception or another language ). If what you are looking for is less than the value of the item found, then you take the half of the current item and the last one checked and no longer need to worry about checking if the item is valid. If you have already found a minor, then when you have to look for a larger one you should consider the half between this item and the larger one previously found.
Another way is to find the size before doing binary search warrant. You can use the same technique or do the classic binary search considering that the imaginary size would be 2 raised to 32. It is the reverse process, whenever the error goes dividing the index by 2, whenever it does not give error take the half. When there is no error try half the time between the one that did not give the error and the last one. With size you make traditional binary search.
Honestly, although I can not prove it, I think this is not a fake problem precisely by the requirement to know when the index bursts. In a data / language structure (any array or types that use array in your implementation in Java, C #, etc.) that can tell you if the is available and just ask. In C, if the programmer knows how to size when mounting an array or other structure based on it. What can happen is that the code intentionally ignores size. Why do this? If I do, I find it impossible to solve. In C, if you throw away the array size, you will not know if you have accessed a place you should not.
Of course you can have specific ways of getting this if the value has a pattern that is guaranteed to not be confused with something else and see if it is still in the array area. Even this, I believe you can not guarantee this.
Otherwise, demonstrate the real need. Show how you would do the simple search in this case to see if we can turn it into a binary search.
