Optimization: implementing a binary search
Searching in a list occurs in a lot of programs. The lazy approach - the one I will normally use in almost all cases - is to just use the default IndexOf method (I am mostly using C# nowadays). However, this gets quickly inefficient if the number of searches starts climbing - IndexOf is a linear search and the inefficiency adds up. If the list is sorted, a binary search will be orders of magnitude faster. (I cannot emphasize enough how important this is - binary search will return incorrect results if the list is not sorted.) The description of the algorithm is as follows: start with the whole list; let l and r be the first and last indices in the interval to search (defaulting to 0 and list.Count - 1 ) let m = the middle of the l .. r interval if the item at index m is equal to the value we're searching, success: return m otherwise, if the item is lower than the value, we need to focus on the upper half of the list; set l = m + 1 if the item is higher than the valu...