C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search

Concept Overview

Binary Search works on the divide-and-conquer principle.
It repeatedly divides a sorted array into halves and determines which half contains the target element.

How It Works (Step-by-Step)

Suppose you have a sorted array:

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

You want to find 23.

  1. Low = 0, High = 9
    → Mid = (0 + 9) / 2 = 4
    → arr[4] = 16 (target > 16) → search right half.
  2. Low = 5, High = 9
    → Mid = (5 + 9) / 2 = 7
    → arr[7] = 56 (target < 56) → search left half.
  3. Low = 5, High = 6
    → Mid = (5 + 6) / 2 = 5
    → arr[5] = 23 →  Element found!

 

C Program: Binary search

Method 1 : Binary Search (Iterative)

C 
#include <stdio.h>


 


// Function for Binary Search


int binarySearch(int arr[], int n, int key) {


    int low = 0, high = n - 1;


 


    while (low <= high) {


        int mid = (low + high) / 2;


 


        if (arr[mid] == key)


            return mid;  // Element found


        else if (arr[mid] < key)


            low = mid + 1;  // Search right half


        else


            high = mid - 1; // Search left half


    }


 


    return -1; // Element not found


}


 


int main() {


    int n, key;


    printf("Enter number of elements: ");


    scanf("%d", &n);


 


    int arr[n];


    printf("Enter %d elements (sorted):\n", n);


    for (int i = 0; i < n; i++)


        scanf("%d", &arr[i]);


 


    printf("Enter element to search: ");


    scanf("%d", &key);


 


    int result = binarySearch(arr, n, key);


 


    if (result != -1)


        printf("Element %d found at index %d\n", key, result);


    else


        printf("Element %d not found in the array\n", key);


 


    return 0;


}

Output

 
INPUT :
Enter number of elements: 10
Enter 10 elements (sorted):
2 5 8 12 16 23 38 56 72 91
Enter element to search: 23

OUTPUT :
Element 23 found at index 5

C Program: Binary search

Method 2 : Recursive Version (Alternative)

C 
#include <stdio.h>


 


int binarySearchRecursive(int arr[], int low, int high, int key) {


    if (low <= high) {


        int mid = (low + high) / 2;


 


        if (arr[mid] == key)


            return mid;


        else if (arr[mid] < key)


            return binarySearchRecursive(arr, mid + 1, high, key);


        else


            return binarySearchRecursive(arr, low, mid - 1, key);


    }


    return -1;


}


 


int main() {


    int n, key;


    printf("Enter number of elements: ");


    scanf("%d", &n);


 


    int arr[n];


    printf("Enter %d elements (sorted):\n", n);


    for (int i = 0; i < n; i++)


        scanf("%d", &arr[i]);


 


    printf("Enter element to search: ");


    scanf("%d", &key);


 


    int result = binarySearchRecursive(arr, 0, n - 1, key);


 


    if (result != -1)


        printf("Element %d found at index %d\n", key, result);


    else


        printf("Element %d not found in the array\n", key);


 


    return 0;


}

Output

 
INPUT :
Enter number of elements: 10
Enter 10 elements (sorted):
2 5 8 12 16 23 38 56 72 91
Enter element to search: 23

OUTPUT :
Element 23 found at index 5

 

Time and Space Complexity

Case

Time Complexity

Space Complexity

Best Case

O(1)

  

Average Case

O(log n)

  

Worst Case

O(log n)

  

Space (Iterative)

O(1)

  

Space (Recursive)

O(log n)

  

Key Takeaways

  • Works only on sorted
  • Time-efficient — reduces search space by half each step
  • Iterative version uses constant space.
  • Recursive version is easier to understand but uses stack memory.
  • Widely used in search engines, databases, and symbol tables.

 

Previous
Next