JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Is there an easier way than binary search if I don't want to find the index? | Reply
I just want to verify that a given input can be found in a constant set, and don't need to find out where in the set it is. Is there a better way than binary search?
I tried minimal perfect hashing function, but it is still not the best in terms of memory space and computational time. In fact, I do not need the function to be minimal perfect, since collision is OK.
Thank you!
Re: Is there an easier way than binary search if I don't want to find the index? (response to post by ctian) | Reply
Binary search (or holding the set in a balanced binary search tree) is just one way to do it. Hashing is more optimal with respect to time, and putting all the values in a list and iterating them until you find the right one or get to the end of the list is the easy but slower way.
Re: Is there an easier way than binary search if I don't want to find the index? (response to post by ctian) | Reply
For hashing you need to have all the values. Binary search also works on functions (predicates) for which you don't have the value before hand so you don't have to evaluate it in every point.
Re: Is there an easier way than binary search if I don't want to find the index? (response to post by dskloet) | Reply
Yes, I do have all the values before hand. That is another reason that I think I can find a better algorithm with regard to space and speed. Is there a way that I can extract information from the existing values to save space, then find a key-index relationship like hashing?
Re: Is there an easier way than binary search if I don't want to find the index? (response to post by ctian) | Reply
Binary Search is a proficient calculation for finding a thing from a requested rundown of things.
Re: Is there an easier way than binary search if I don't want to find the index? (response to post by ctian) | Reply
Twofold Search might be a decent count for finding a factor from an asked for summation of factor It works by again and again logical into break even with parts the smidgen of the summation that would contain the thing, till you have limited the possible ranges to only one.
RSS