A List<T>.BinarySearch extension that takes a lambda expression

I was thinking the other day how inconvenient it is to use List<T>.BinarySearch if you don't want to use the default comparer of T, needing to go and create a new class that implements IComparer<T>. Seems overly messy to require a whole new class just to do the binary search.

So I did a little research to see if there was a way around it and found this Jon Skeet answer (obviously) on StackOverflow. It gives a nice generic class that we can instantiate with a Comparison object and pass that into the BinarySearch method. I extended Jon's answer to take a lambda expression instead, much like you can do with List.Sort.

Algorithm: Binary search

Binary search is a decrease and conquer search algorithm than can be used on a sorted array. It operates by determining whether the search value is less than or greater than the middle value and recursively calling itself on the lower or upper half of the list respectively until either the value is found or not found.

The binary search algorithm is very similar to the binary search tree's search operation though not identical. Binary search's average and worst case time complexity is O(log n), while binary search tree does have an average case of O(log n), it has a worst case of O(n). Namely when the tree's height equals the number of items in the tree (incredibly unlikely in any real scenario).

The real power in binary search shows itself when we use it to search a huge list of items, much like any logarithmic algorithm. Exponential functions work by looking at the whole input data when considering each item. Logarithms (inverse-exponential functions) work by repeatedly halving the input data. Consider a list that contains 1 million items, if this list happens to be sorted we can use binary search to search for an item in no more than 20 steps.

Big-O Notation

Introduction

Big-O notation (pronounced 'Big Oh') is used in computer science as a means to describe the worst-case performance of an algorithm. It's one of the things you really should learn if you're interested at all in designing efficient algorithms.

The formal definition is as follows:

f(n) = O(g(n)) means c*g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c*g(n), for large enough n (i.e. , n ≥ n₀ for some constant n₀).

The Algorithm Design Manual, Steven S. Skiena

This definition is a very format way of saying that Big O-notation is the upper-bound/worst-case of a function.

The A* pathfinding algorithm

Game development introduced me to programming when I was around 10, and I've loved it ever since. One of the first formal algorithms I learned before entering university was A* (pronounced A-star), and I really had a great time doing so. It is one of the most widely used pathfinding algorithms and it's likely the one you'd be introduced to first when approaching the subject of pathfinding. A pathfinding algorithm takes a start point (also referred to as a node) and a goal and attempts to make the shortest path between the two given possible obstacles blocking the way.