jaanu.cheruvu

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.

Salem 5,138

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

You have n sorted integers.

jaanu.cheruvu

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.

ArkM 1,090

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

jaanu.cheruvu

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

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

Rashakil Fol 978

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.

jaanu.cheruvu

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

nucleon 114

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

jaanu.cheruvu

> 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