Binary Search Algorithm Using C#

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
    }
}

Try Out

 

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.