C# best approach to search big List<T> faster

Question

i have for loop which has big iteration and with in for loop i am searching a big List<T> repeatedly for each iteration with in for loop.
this way i am searching which is may not be efficient way and i realize program taking long time to complete. i doubt searching large List<T> with for loop causing this delay to complete the program execution.

    string _startperiod = ""

    if (listOfCell.Any(a => a.Period.Replace("A", "").Replace("E", "") == period.Replace("A", "").Replace("E", "") && a.PeriodType == "BROKER_COUNT"))
    {
        _startperiod = listOfCell.Where(a =>
        a.Period.Replace("A", "").Replace("E", "") == period.Replace("A", "").Replace("E", "")
        && a.PeriodType == "BROKER_COUNT").FirstOrDefault().CoorDinate;
    }

i searched google on this topic and saw people use these

1) List.BinarySearch(item)

2) According to the results, a BinarySearch on a List and SortedList were the top performers constantly running neck-in-neck when looking up something as a "value".

3) SortedSet<T> Class & ImmutableSortedSet

4) List<T>.Find(Predicate<T>) should i search List<T> this way for better performance ?

List<T>.Find(Predicate<T>) will be faster or List<T>.BinarySearch(item) will be faster if my List<T> has million data ?

please tell me how to perform List<T>.BinarySearch(item). provide some code example.

please suggest best practice. thanks

Answer 1

@T.Zacks , We can compare with their Algorithm complexity to know which is faster.

From the doc List<T>.BinarySearch Method-Remarks and List<T>.Find(Predicate<T>) Method, we could find the following sentence:

This method is an O(log n) operation, where n is the number of elements in the range.(List<T>.BinarySearch)

This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.(List<T>.Find)

From the link Difference between O(n) and O(log(n)) - which is better and what exactly is O(log(n))?

We can know O(log n) is better than O(n), therefore List<T>.BinarySearch will be faster than List<T>.Find.

The code example about List<T>.BinarySearch. you could refer to the Microsoft-link: List<T>.BinarySearch Method-Examples

Best Regards,
Jack

---

If the answer is the right solution, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.

Answer 2

~index is the complement of the index value (~0 < 0). the binary search returns not found index as a negative of the correct insert position,

A binary search only works with a sorted list of unique keys.

As you are modifying the values as you search, a binary search will not work, if you do the search more than once, you could pre-sort by the derived key (which must be unique) and save for binary search . a sort takes longer than a search , so its only useful if done more than once.

// build the sorted list and keys - only do once - maybe store as static
var sortedList = listOfCell.Where(a => a.PeriodType == "BROKER_COUNT").OrderBy(c => c.Period.Replace("A", "").Replace("E", "")).ToList();
var sortedKey = sortedList.Select(c => c.Period.Replace("A", "").Replace("E", "")).ToList();


// now lookup
var lookup = "some value";
var index = sortedKey.BinarySearch(lookup.Replace("A", "").Replace("E", ""));
if (index >= 0)
    Console.WriteLine($"{index} {sortedList[index].Period}");
else
    Console.WriteLine("Not Found");