### 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 intervalif the item at index m is equal to the value we're searching, success: return motherwise, if the item is lower than the value, we need to focus on the upper half of the list; set l = m + 1if the item is higher than the value we need the lower h…