CODEWITHSUNDEEP
cperformancealgorithm
Pierre
Pierre

Reputation: 394

Fast binary search/indexing in c

I have a dataset composed of n Elements of a fixed size (24 bytes). I want to create an index to be able to search as fast as possible a random element of 24 bytes in this dataset. What algorithm should I use ? Do you know a C library implementing this ?

fast read access/search speed is the priority. Memory usage and insertion speed is not a problem, there will be barely no write access after the initialization.

EDIT: The dataset will be stored in memory (RAM) no disk access.

Upvotes: 3

Views: 1077

Answers (2)

user1196549
user1196549

Reputation:

Use a hash table, available as a std::unordered_map in STL. Will beat a binary search (my bet).

Alternatively, a (compressed) trie (http://en.wikipedia.org/wiki/Trie). This is really the fastest if you can afford the memory space.

Upvotes: 1

Sean
Sean

Reputation: 62472

If there's a logical ordering between the elements then a quick sort of the data is a fast way to order the data. Once it's ordered you can then use a binary search algorithm to look for elements. This is a O(log N) search, and you'll be hard pressed to get anything faster!

std::sort can be used to sort the data, and std::binary_search can be used to search the data.

Upvotes: 3

Related Questions