0

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.

5
Contributors
8
Replies
9
Views
7 Years
Discussion Span
Last Post by jaanu.cheruvu
0

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.

0

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

0

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

0

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.

0

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

0

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

0

> 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

This question has already been answered. Start a new discussion instead.
Please be thoughtful and detailed and be sure to adhere to our posting rules.