Binary search is another well known searching algorithm. In plain terms, a binary search starts at the midpoint of a list or collection and compares a search term or key with the midpoint term, so in example:

List = 1, 4, 6, 8, 10, 18, 32 Value to look for: X = 4

First run: compare X with 8 (the middle value). Its smaller, repeat search with 1, 4, 6

Second run: compare X with 6. Its smaller, repeat with 1, 4

Third run: compare X with 4. Search is done, we have found 4.

- The Binary search has O(log(n)) complexity, making it more efficient in the long run with larger data collections unlike the Linear Sort which is more desirable with smaller, unsorted data collections. Its O(log(n)) because it halves the number of items to search with each iteration
**For a binary search to begin, the collection MUST be sorted first and foremost**

The binary search implementation:

class Program { static void Main() { int[] collection = { 1, 3, 5, 7, 9, 11, 21 }; //our collection is already sorted for (int i = 0; i < collection.Length; i++) { Console.Write("{0} ", collection[i]); }//first, we write all the elements of the collection on the window so we can see the list Console.WriteLine(); Console.Write("Enter a value to search for in the collection: "); int searchKey = int.Parse(Console.ReadLine()); int middle; int maximum = collection.Length; int minimum = 0; while (minimum <= maximum) { middle = (maximum + minimum) / 2; if (collection[middle] == searchKey) { Console.WriteLine("\nElement {0} was found at position {1} in the collection!", searchKey, middle); break; } else if (collection[middle] > searchKey) { maximum = middle - 1; } else if (collection[middle] < searchKey) { minimum = middle + 1; } else { Console.WriteLine("The value does not exist"); break; } } Console.ReadLine(); } }

Further illustrations:

Advertisements