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.
jaanu.cheruvu 0 Newbie Poster
Salem 5,199 Posting Sage
So what's with all the smoke about "infinity" then?
You have n sorted integers.
jaanu.cheruvu 0 Newbie Poster
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 Postaholic
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 0 Newbie Poster
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
...
Rashakil Fol 978 Super Senior Demiposter Team Colleague
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 0 Newbie Poster
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 Posting Pro in Training
> 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 0 Newbie Poster
> it takes so much of time to find a number greater
> than searching numberThat'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
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.