Searching for an element in a dataset is a common task in programming. Unlike linear search, binary search is a faster method that works on sorted arrays. It repeatedly divides the array in half, checking the middle element each time, until the desired value is found or the search space is empty. Binary search is more efficient than linear search for large datasets because it reduces the number of comparisons significantly. In this tutorial, we will write a C program to perform binary search.
Binary search requires the array to be sorted. If the array is not sorted, the search may produce incorrect results. Understanding binary search also helps you learn how algorithms can optimize performance. By learning this technique, you develop a foundation for more advanced searching and sorting methods in C, such as interpolation search or search trees.
Understanding the Problem
Binary search relies on the array being sorted. The algorithm compares the target element with the middle element of the array. If they match, the search is complete. If the target is smaller, the search continues in the left half; if larger, in the right half. Both iterative and recursive implementations follow this logic, with recursion handling the search through successive function calls.
Program 1: Iterative Binary Search
This program demonstrates searching for an element in a sorted array using a loop. The function returns the index if the element is found or -1 if not found.
#include <stdio.h>
#include <stdlib.h>
// Compare function for qsort
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
// Iterative binary search function
int binarySearchIterative(int arr[], int size, int key) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {50, 20, 40, 10, 30};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 40;
// Intent: Binary search requires a sorted array.
// Action: Sort the array using qsort if it isn’t already sorted.
qsort(arr, size, sizeof(int), compare);
int result = binarySearchIterative(arr, size, key);
if (result != -1)
printf("%d found at index %d\n", key, result);
else
printf("%d not found in the array\n", key);
return 0;
}The iterative method reduces the search space using two pointers (left and right). It repeatedly checks the middle element, adjusting pointers until the element is found or the search space is exhausted.
Program 2: Recursive Binary Search
This program demonstrates binary search using recursion. Each recursive call narrows the search space until the element is found or the base case is reached.
#include <stdio.h>
#include <stdlib.h>
// Compare function for qsort
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
// Recursive binary search function
int binarySearchRecursive(int arr[], int left, int right, int key) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
return binarySearchRecursive(arr, mid + 1, right, key);
else
return binarySearchRecursive(arr, left, mid - 1, key);
}
int main() {
int arr[] = {50, 20, 40, 10, 30};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 50;
// Intent: Binary search requires a sorted array.
// Action: Sort the array using qsort if it isn’t already sorted.
qsort(arr, size, sizeof(int), compare);
int result = binarySearchRecursive(arr, 0, size - 1, key);
if (result != -1)
printf("%d found at index %d\n", key, result);
else
printf("%d not found in the array\n", key);
return 0;
}In the recursive approach, each call reduces the search space by half, passing updated left and right indices. Recursion continues until the element is found or the indices cross, signaling the element is absent.
FAQs
Q1: What is the time complexity of binary search?
The time complexity is O(log n) for both iterative and recursive approaches.
Q2: Can binary search be used on unsorted arrays?
No, the array must be sorted for binary search to work correctly.
Q3: Which method is better: iterative or recursive?
Iterative binary search is generally preferred for large arrays to avoid stack overflow from recursion.
Q4: Can binary search find multiple occurrences of a value?
By default, it finds one occurrence. Modified binary search can locate first and last occurrences efficiently.
Conclusion
Binary search is a fast and efficient searching algorithm for sorted datasets. Understanding both iterative and recursive implementations helps strengthen problem-solving and algorithmic skills. Proper handling of base cases and middle index calculation ensures correct results for all inputs.
References & Additional Resources
A curated collection of classic and modern resources exploring binary search in C programming and algorithm theory.
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A traditional and respected textbook covering core C concepts and fundamental data structures, including search algorithms.
- Binary Search – GeeksforGeeks – A clear and practical explanation of the binary search algorithm using divide-and-conquer, showing how sorted arrays are halved each step to locate a target efficiently.
- Binary Search – Programiz – Step-by-step guide that walks through how binary search works with both iterative and recursive implementations.
- Exploring Time and Space Complexities of Binary Search – Programiz PRO – Analytical deep-dive into best-case (O(1)), average-/worst-case (O(log n)) time complexities, and constant space usage (O(1)).
- Binary Search – Wikipedia – A technical overview featuring pseudocode, boundary cases, algorithm variations, and real-world implications.
- Searching Algorithms – GeeksforGeeks – Broader tutorial covering both linear and binary search, comparing when each is best applied.
