What is a binary search

Binary search is an efficient search algorithm that finds the position of the target value in a sorted array. Let's take a look at an example.

Example

Suppose you're searching a number 88 in a sorted array [5, 23, 56, 70, 88, 90]. You could search linearly starting from the beginning of the array until you find the number or until you reach the end of the array.

The linear search can be implemented like this. The Search method returns the index of the target value if the target value exists, otherwise it returns -1.

   public int Search(int[] array, int target)
   {
       for (int i = 0; i < array.Length; i++)
       {
           if (array[i] == target)
           {
               return i;
           }
       }
   
       return -1;
   }

The algorithm works, but it ignores the fact that the array is sorted. Let's try to use it to our advantage.

The idea is to check the value in the middle of the array:

  • if the middle value is greater than the target value, continue searching in the left half
  • if the middle value is smaller than the target value, continue searching in the right half
  • if the middle value is equal to the target value, return the index of the middle value

The middle value of the array is 56. 56 is less than 88, which mean the target value could be in the right half. 88 cannot be in the left half because the array is sorted -- all values to the left of 56 are smaller than 56 and therefore are also smaller less than 88. After the first step, we need to check only values from 70 to 90. The next middle value is 88, so we return index 4.

Let's go through this process step by step again:

  • Initial: array = [5, 23, 56, 70, 88, 90], target = 88
  • middle value = 56, 56 < 88, searching in the right half of the array [5, 23, 56, 70, 88, 90]
  • middle value = 88, 88 is equal to the target value, hence return the index of the array 4

Here's an iterative implementation of the binary search:

    public int Search(int[] array, int target)
    {
        int low = 0;
        int high = array.Length - 1;
        while (low <= high)
        {
            int middle = low + (high - low) / 2;
            if (array[middle] > target)
            {
                high = middle - 1;
            }
            else if (array[middle] < target)
            {
                low = middle + 1;
            }
            else
            {
                return middle;
            }
        }

        return -1;
    }