Binary Search in C

May 24, 2022

Binary Search in C

Binary search is a very fast and efficient searching algorithm. It requires to be list be in sorted order, ie; either in ascending or descending.

Lets have a look at binary search below –

Binary Search
Time Complexity (Best) Ω(1)
Time Complexity (Avg) Θ(log n)
Time Complexity (Worst) O(log n)
Space Complexity O(1)

How Binary Search in C works?

  1. The array needs to be sorted in either ascending or descending order
  2. In our case we are taking an example for an array sorted in ascending order.
  3. The searching algorithm proceed from any of two halves
  4. Depends upon whether the element you are searching is greater or smaller than the central element
  5. If the element is small then, searching is done in first half
  6. If it is big then searching is done in second half. 

It is fast search algorithm with the complexity of O(log n).

Binary Search in C Intro

Implementation of Binary Search

  • Take a sorted array (mandatory) 
  • Find mid using formula m = (l+r)/2
  • If the item to be searched is greater than mid
    • Check the right subarray
  • If the item to be searched is lesser than the mid
    • Check the left subarray
  • If mid element == item return with the position where found
  • Else keep doing the above steps until you violate the bounds of the array
Binary Search in C

Methods Discussed

We are going to be discussing two methods here –

  • Method 1: Recursive Approach
  • Method 2: Iterative Approach

Binary Search in C (Recursive Approach)

Note – This method uses recursion in C.

Run 
// Binary Search implimentation in C (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include <stdio.h>

int binarySearch(int arr[], int left, int right, int item){
    
    if (right >= left){
        
        // calculation of new mid
        int mid = left + (right - left)/2;

        // returns position where found
        if (arr[mid] == item)
            return mid;
        
        // goes to recursive calls in left half
        if (arr[mid] > item)
            return binarySearch(arr, left, mid-1, item);
    
        // goes to recursive calls in right half
        else
            return binarySearch(arr, mid+1, right, item);
    }
    // if element is not found we return -1
    else
       return -1;
}
int main(){
    // array needs to be sorted to impliment binary search
    int arr[8] = {10, 20, 30, 40, 50, 60, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int item = 70;
   
    int position = binarySearch(arr, 0, n-1, item);

    if(position == -1)
        printf("%d Not Found",item);
    else
        printf("%d Found at index : %d",item, position);
}

Output:-

70 Found at index : 6

Binary Search in C (Iterative Approach)

Let’s look at this approach below

Run 
// Binary Search implimentation in C (Iterative)
// Time Complexity : O(N)
// Space Complexity : O(1)
#include <stdio.h>

// Returns index of item in given array, if it is present
// otherwise returns -1
int binarySearch(int arr[], int l, int r, int item)
{
    while (l <= r) {
        int mid = l + (r - l) / 2;
  
        // if item is at mid
        if (arr[mid] == item)
            return mid;
  
        // If item greater, ignore left half, consider only right half
        if (arr[mid] < item)
            l = mid + 1;
  
        // If item is smaller, ignore right half, consider only left half
        else
            r = mid - 1;
    }
  
    // if we are able to reach here
    // means item wasn't present
    return -1;
}
  
int main(void)
{
    // array needs to be sorted to impliment binary search
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int item = 30;
    
    int position = binarySearch(arr, 0, n - 1, item);
    
    if(position == -1)
        printf("%d Not Found",item);
    else
        printf("%d Found at index : %d",item, position);
        
    return 0;
}

Output

30 Found at index : 2
Binary Search in C Example
Binary Search in C Meme

Time Complexity
For Binary Search

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space Complexity

O(1)

Average Comparisions

Log(N+1)

Quiz time

Quiz Time

Question 1.Binary search algorithm can’t be applied to

  1. Pointed Array List
  2. Sorted Binary Tree
  3. Unordered Array
  4. Sorted Linked List

(Cisco, Walmart Labs)

You cannot use a binary search on an unsorted list. Your best bet is to probably iterate over the list’s items until you find the element you are looking for, an O(n) operation, i.e. do linear search

Ans. C

Question 2. Which is the following searching algorithms works on the divide and conquer?

  1. Binary Search
  2. Linear
  3. Sequential
  4. Merge Sort

(CoCubes, Atos Syntel)

Binary search only checks the middle element of the array. when it checks the middle element and middle element is not equal to the given element then we divide the list in two subparts.

Ans: Both A & D

Data Structures and Algorithm Learn Searching PrepInsta

Searching

Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.