loader image
Teachics

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.

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.

binary search array to be searched
Array to be searched

Set two pointers low and high.

binary search setting pointers
Setting low and high pointers

Find the middle element of the array.

binary search mid element 1
Finding the middle element

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 .

binary search finding new mid
Updating low and high pointers

Now repeat the same steps until low meets high.

binary search found new mid
New mid element

x = mid =3, element is found.

binary search element found
Element 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.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments