Binary Search

In this tutorial, you will learn about how the binary search algorithm works and its implementation using C.

Searching is the process of finding whether or not a specific value exists in an array. The binary search algorithm can be used to search for an element in a sorted array.

Working of Binary Search

The binary search algorithm works as follows:

• The array is divided into two halves by a middle element.
• If the element is found in the middle, the position is returned; otherwise
  • If the value is less than the middle, then the first half of the array is searched.
  • If the value is greater than the middle, then the second half of the array is searched.

Consider the following array of 7 elements where we have to search for element 3.

Set two pointers low and high.

Find the middle element of the array.

Since the item is less than the middle element, ie 3 < 5 , we have to search in the first half of the array. This is done by updating the high pointer as high = mid - 1 .

Now repeat the same steps until low meets high.

x = mid =3, element is found.

Binary Search Algorithm

1: SET LOW = 0, HIGH = SIZE-1, POS=-1
2: Repeat Steps 3 and 4 while LOW <= HIGH
3: SET MID = (LOW + HIGH)/2
4: IF A[MID] = VAL
‎      SET POS = MID
‎ ‎     PRINT POS
‎      Go to Step 6
‎   ELSE IF A[MID] > VAL
‎      SET HIGH = MID-1
‎   ELSE
‎      SET LOW = MID+1
‎   [END OF IF]
‎   [END OF LOOP]
5: IF POS=-1
‎      PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
‎   [END OF IF]
6: EXIT

C Example

The binary search algorithm can be implemented in C as follows:

// Binary search in C
#include <stdio.h>

int main(void) 
{ 
    int arr[7] = {2, 3, 4, 5, 6, 7, 8};
    int n=7, x=3, low=0, high=n-1, pos=-1;

    while (low <= high) { 
        int mid = low + (high) / 2; 
   
        if (arr[mid] == x) 
            pos=mid; 
   
        if (arr[mid] < x) 
            low = mid + 1; 
        else
            high = mid - 1; 
    } 
    if(pos == -1)
        printf("Element not found in array");
    else
        printf("Element found at position %d", pos+1); 
    return 0; 
}

Binary Search Complexity

The binary search takes O(log n) time to execute, where n is the number of elements in the array.