**Binary search** is the most popular and efficient search algorithm used to solve problems. It tries to find the desired element in a list by dividing the list into left and right sub-lists.

Think of this as our childhood game : guessing a number between 1 and 100 played by us where we used to guess the number and instructor used to tell whether you need to guess higher or lower.

Intuitively, We start with guessing the number 50, because by selecting 50, no matter whether guess correctly or wrongly, we automatically eliminates half the possible numbers because now we need to guess a number between 1 and 50 or 50 to 100 based on suggestion by instructor weather the desired number is higher or lower in value.

This is what binary search do while searching for any element.

Prior to performing binary search algorithm, the collection must first be sorted.

##### Pseudo Code:

- Check the middle element of the list. If found the element we are searching for, we are done.
- If the middle element is smaller than the value we are searching for, then search on the right sub-list of the middle element. This is because everything on the left is even smaller.
- If the middle element is bigger than the value we are searching for, then search only in the left sub-list.

##### C# Implementation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | using System; public class Program { public static void Main() { int searchInt; // seach key int position; // location of search key in array int[] data = {1,4,5,8,9,13,17,22,24,25,33,54,67,72,77,88,90,93,95,97,99}; // prompt and input first int from user Console.Write("Please enter an integer value (-1 to quit): "); searchInt = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); // repeatedly input an integer; -1 terminates the application while (searchInt != -1) { // use binary search to try to find integer position = BinarySearch(data,searchInt); // return value of -1 indicates integer was not found if (position == -1) Console.WriteLine("The integer {0} was not found.\n", searchInt); else Console.WriteLine("The integer {0} was found in position {1}.\n", searchInt, position); // Prompt and input next int from user Console.WriteLine("Please enter an integer value (-1 to quit): "); searchInt = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); } } // perform a binary search on array public static int BinarySearch(int[] data, int searchElement) { int low = 0; // 0 is always going to be the first element int high = data.Length - 1; // Find highest element int middle = (low + high + 1) / 2; // Find middle element int location = -1; // Return value -1 if not found do // Search for element { // output spaces for alignment for (int i = 0; i < middle; i++) Console.Write(" "); Console.WriteLine(" * "); // Indicate current middle // if element is found at middle if (searchElement == data[middle]) location = middle; // location is current middle // middle element is too high else if (searchElement < data[middle]) high = middle - 1; // eliminate lower half else // middle element is too low low = middle + 1; // eleminate lower half middle = (low + high + 1) / 2; // recalculate the middle } while ((low <= high) && (location == -1)); return location; // return location of search key } } |

So, it was all about Binary Search Algorithm, if you have any query then please comment below and let us know. If you liked this article, then please follow us on Facebook to get notification for new posts.

Happy Learning 🙂

Rahul is a Data Geek, technology enthusiast, a passionate writer, thinker with passion for computer programming. He loves to explore technology and finds ultimate joy when writing about trending technology, geek stuff and web development.