Infinity array problem

So what's with all the smoke about "infinity" then?

You have n sorted integers.

So what's with all the smoke about "infinity" then?

You have n sorted integers.

first list contain n integers then remaining all are garbage values.
Don't use traversing the list to find n.

Evidently it's impossible in terms of element access counter because no direct access to list elements so you need ~n/2 accesses to fetch a given number from a list - O(n) time complexity.

If n denotes a number of comparisons - it's the other story. It's so simple ;)...

PS. List or array? Array in the header, list in the body...

Evidently it's impossible in terms of element access counter because no direct access to list elements so you need ~n/2 accesses to fetch a given number from a list - O(n) time complexity.

If n denotes a number of comparisons - it's the other story. It's so simple ;)...

PS. List or array? Array in the header, list in the body...

Thanks for u'r reply..

I am not asking the complexity, i wanna know logic to implement
...

Presumably he has random access to the list; otherwise this problem would be impossible.

The answer is pretty simple, and we're not just going to give you the answer.

Here's a hint though: There obviously must be some way to find a value _greater_ than the one you're searching for, in O(log n) time.

Presumably he has random access to the list; otherwise this problem would be impossible.

Here's a hint though: There obviously must be some way to find a value _greater_ than the one you're searching for, in O(log n) time.

it takes so much of time to find a number greater than searching number

> it takes so much of time to find a number greater
> than searching number

That's the heart of the problem. How do you decrease that time? You definitely don't want to do a linear search!

I guess I understand the "infinity" stuff. It means that you can access any index whatsoever without an error. This could be implemented as a function that returns the element value for indices up to n-1 but returns "infinity" (say max int) otherwise.

The question is basically "how do you do a binary search (or similar) on an infinite array"? Obviously you can't start in the "middle", so you need to consider other options.

> it takes so much of time to find a number greater
> than searching number

That's the heart of the problem. How do you decrease that time? You definitely don't want to do a linear search!

I guess I understand the "infinity" stuff. It means that you can access any index whatsoever without an error. This could be implemented as a function that returns the element value for indices up to n-1 but returns "infinity" (say max int) otherwise.

The question is basically "how do you do a binary search (or similar) on an infinite array"? Obviously you can't start in the "middle", so you need to consider other options.

okkk thanks a lot