Write C code to implement the Binary Search algorithm

Binary search is used to quickly find a value in a sorted sequence.At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.

In the example given above, we are searching “cat” in sorted array. In each step, algorithm is eliminating half of the elements.

int binarySearch(int arr[],int size, int item)
{
   int left, right, middle;
   left  = 0;
   right = size-1;

   while(left<=right)
   {
      middle = ((left + right)/2);

      if(item == arr[middle])
      {
        return(middle);
      }
      
      if(item > arr[middle])
      {
        left  = middle+1;
      }
      else
      {
        right = middle-1;
      }
   }

   return(-1);
}

Note: This algorithm will not work on an unsorted array.

Complexity:

• Worst case performance O(log n)
• Best case performance O(1)
• Average case performance O(log n)
• Worst case space complexity O(1)