Binary Search using C#

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

• Each step 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 does not match any of the subsequent left or right arrays, 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);  
           }  
      }  
 }

The above code is a recursive implementation of the binary search algorithm. Binary search is a divide-and-conquer algorithm that can be used to search for a value in a sorted array.

The code first checks if the minimum value is greater than the maximum value. If it is, then the value is not found in the array, and the function returns "Nil". Otherwise, the code calculates the middle index of the array and compares the value to the element at the middle index.

If the value is equal to the element at the middle index, then the function returns the index of the element. Otherwise, the code recursively calls itself on the half of the array that does not contain the value.

The recursive call to the function continues until the value is found or the minimum value is greater than the maximum value.

Here is an explanation of the code step-by-step:

1. The function takes the input array, the key to search for, and the minimum and maximum values of the array as input.
2. The function checks if the minimum value is greater than the maximum value. If it is, then the value is not found in the array, and the function returns "Nil".
3. Otherwise, the function calculates the middle index of the array.
4. The function compares the value to the element at the middle index.
5. If the value is equal to the element at the middle index, then the function returns the index of the element.
6. Otherwise, the function recursively calls itself on the half of the array that does not contain the value.
7. The recursive call to the function continues until the value is found or the minimum value is greater than the maximum value.