CODEWITHSUNDEEP
c#listdata-structuresstruct
Amin
Amin

Reputation: 129

Search a record in a list without scanning all of records

I have a List of an Record(structure) like this :

struct Rec
{
     int WordID;
     int NextID;
     int PrevID;
}

List<Rec>= New List<Rec>(){...};

I need a way to find a value of "Rec" type in List without search all of records like Binary search. I want it's time complexity be less than O(n)

Upvotes: 0

Views: 280

Answers (2)

Salvatore Previti
Salvatore Previti

Reputation: 9060

The best way to search for an item in a list is of course not having a list but having an hashtable.

If you have a dictionary instead of a list (or a dictionary AND a list) you can perform search for exact values in averaged\amortized O(1).

You can also use a binary search but only if the list is sorted, there is the method List<T>.BinarySearch and the search with be O(log n).

Sorting a list with n items is O(n log n). Inserting n items in an hashtable instead is averaged O(n), inserting an item is averaged O(1). This means that also creating the hashtable (or keeping the hashtable synchronized with the list) will be faster than sorting a list. Consider however that hashtable consumes more memory because they have to keep internally a bucket array.

Upvotes: 2

Jakub Konecki
Jakub Konecki

Reputation: 46008

You can use binary search providing your list is sorted.

Upvotes: 1

Related Questions