Infosys | Microsoft

Time taken by a Linear Search over n items is O(n)
Time taken by a Binary Search over n item is O(log₂n)
Time taken to sort n items is O(n x log₂n)

To simplify, for a value of n = 256,

An indicative Linear Search time for 1 search operation O(n) is: 383
An indicative Binary Search time for 1 search operation O(n x log₂n) + O(log₂n) is: 2048 + 8 = 2056

After 100 search operations over the same set of items this value becomes,
Linear Search: 383 x 100 = 38300
Binary Search: 2048 (because sort is performed only once) + 8x100 = 2848

Interestingly the decision is not based on the size of n. But rather on the number of Search operations on the item space. Linear Search is fast if the amount of search operations are lesser. When the amount of search operations made on the list increases, the time taken to sort is mitigated (the goodies of economies of scale plays its part in algorithms as well) and Binary Search results as the better option.

Ideally, the choice between Linear and Binary Search should be taken based on the number of search operations that are likely to be performed over the List.

A very useful .NET Type that can come in handy in this situation is SortedList. SortedList is a collection of key/value pairs that are sorted automatically by the keys, as you add items to it. This way you can let the framework sort stuff for you, just before you run a Binary Search.