2

For arrays of finite size, we can use binary search to get the solution in O(log(n)) time.

If we have an infinite array with constant time lookup of indexes, how fast can we find the first occurrence of a 1 if we know the array is sorted?

wildplasser
  • 43,142
  • 8
  • 66
  • 109
ranganath111
  • 457
  • 2
  • 7
  • 17
  • Considering that infinite arrays don't exist in a finite environment as a PC, I would retag this as homework. – Alessandro Santini Jan 06 '13 at 10:53
  • What have you tried so far? Show us what has been your effort in this respect so that we can address properly. – Alessandro Santini Jan 06 '13 at 10:54
  • this is an interview question. plzz dnt think me wrong – ranganath111 Jan 06 '13 at 10:55
  • @ranganath111 Homework question, interview question, it does not matter. Try to solve it yourself and tell us where you're stuck. On this site we generally won't do your work for you. We will help you with practical problems you face. And in its current formulation this is not much of a question to begin with. – Bart Jan 06 '13 at 10:56
  • @AlessandroSantini Maybe it's an array in C where you don't have it's size. (or linked list or lazy list...) – assafmo Jan 06 '13 at 11:02
  • @gfgqtmakia linked lists (circular lists for instance) are not accessible directly but only sequentially, so the question would be pointless; in C, the size of an array is given by sizeof(array) / sizeof(structure stored in the array), if I am not incorrect. – Alessandro Santini Jan 06 '13 at 11:04
  • @AlessandroSantini http://stackoverflow.com/questions/492384/how-to-find-the-sizeofa-pointer-pointing-to-an-array :-) – assafmo Jan 06 '13 at 11:07

1 Answers1

1

What is the above question? What are your operations on the infinite array? O(1) lookup? Perhaps the best thing would be to look iterate up to the first occurrence of a 1 of index 2^n for some n, and then do binary search. Then you are guaranteed to find it in O(log(n)) where n is the position of the first index.

Edit: Ps. This is not guaranteed to terminate if the array is indeed infinite and contains only zeros.

Pål GD
  • 1,021
  • 8
  • 25
  • 1
    No, first you do exponential, basically that you try indices 1,2,4,8,16,32 etc. Then when you hit a one, e.g. at 4096 = 2^12, you do binary search between 2^11 = 2048 and 2^12 = 4096. – Pål GD Jan 06 '13 at 10:55
  • In other words, you try to establish the first useful midpoint (e.g. where value(index) > searched_value) using exponentially growing indexes. – Alessandro Santini Jan 06 '13 at 10:58