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.

Hi Maam and Sir.
I need your expertise on vb.net.
I have two data grid with database on their own. I want to copy/update the data from one database to ...

Hi everyone, I am working on a coin collection app, and I have recently started integrating core data into my app. My app is of the following format: I have ...

I'm creating a warehouse management system, then i want when new orders are created, a customer's name be selected from a list box and that customer's selected name ...