can any1 solve this .....Given a sorted list of infinite size in which first n elements (n is unknown) are finite integers and rest are infinity, write an efficient function that finds a given number in O(ln n ) time complexity.

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
...

> 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.

First of, i didn't know where to post this question as it isn't actually programming based but yeah. sorry.. Anyway, I was going through my binary file trying to figure ...