Binary Search Implementation Using C#

Today we will discuss the Binary Search Algorithm. It is one of the Divide and conquer algorithms types, where in each step, it halves the number of elements it has to search, making the average time complexity to O (log n). It works on a sorted array. Given below are the steps/procedures of the Binary Search algorithm.

• In each step, it compares the search key with the value of the middle element of the array.

• The keys matching in step 1 means, a matching element has been found and its index (or position) is returned. Else step 3 or 4.

• If the search key is less than the middle element, then the algorithm repeats its action on the sub-array to the left of the middle element or,

• If the search key is greater than the middle element, then the algorithm repeats its action on the sub-array to the right of the middle element.

• If the search key is not matching any of the subsequent left or right array, then it means that the key is not present in the array and a special "Nil" indication can be returned.

We will first have a look at the C# implementation using an iterative approach.

public static object BinarySearchIterative(int[] inputArray, int key)
{
  int min = 0;  int max = inputArray.Length - 1;
    while (min <=max)
    {
       int mid = (min + max) / 2;
       if (key == inputArray[mid])
       {
            return ++mid;
       }
       else if (key < inputArray[mid])
       {
           max = mid - 1;
       }
       else
       {
            min = mid + 1;
       }
   }
   return "Nil";
}

And here is the recursive one. Please note that in recursive, you need to pass min as 0 and max as inputArray.Length - 1

public static object BinarySearchRecursive(int [] inputArray, int key, int min, int max)
{
      if (min > max)
      {
          return "Nil";
      }
      else
      {
          int mid = (min+max)/2;
          if (key == inputArray [mid])
          {
             return ++mid;
           }
           else if (key < inputArray [mid])
           {
               return BinarySearchRecursive(inputArray, key, min, mid - 1);
           }
           else
           {
              return BinarySearchRecursive(inputArray, key, mid + 1, max);
           }
      }
 }