4

Suppose, the array is infinite. So, the problem here is that we don’t know the size of the array. If the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to find the position of the key, what can I do.

Improve this question

1 Answer 1

Reset to default
2

It will no longer qualify as a pure binary search, but here's one approach.

For an array array and a search value s:

  1. Decide on a block size n (e.g. n = 1000)
    Define an initial index i corresponding to the first element in the array (i = 1)
  2. Compare the search value s to the value at array[n]
  3. Then:
    1. If array[n] is greater than s:
      Continue with a regular binary search between array[i] and array[n]
    2. If array[n] is less than s:
      Move the index: i = i + n
      Double the block size: n = n * 2
      Start over at step 2.
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.