Tag sorted array

Binary Search in C: A Comprehensive Tutorial

Binary Search is a fundamental searching algorithm that operates on a sorted or monotonic search space, repeatedly dividing it into halves to find a target value or optimal answer in logarithmic time O(log N). It is one of the most important algorithms in computer science and forms the foundation for many advanced algorithms and data structures.

This tutorial provides an in-depth exploration of Binary Search in C: algorithm principles, iterative and recursive implementations, complexity analysis, practical applications, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is Binary Search?

Binary Search is a divide-and-conquer algorithm that finds the position of a target value within a sorted array. It compares the target with the middle element of the array and eliminates half of the search space based on the comparison.

Why Binary Search Matters

• Efficiency: O(log n) time — exponentially faster than linear search.
• Foundation: Basis for many algorithms and data structures (BST, B-trees).
• Wide applications: Databases, debugging, network routing, machine learning.
• Interview preparation: Very common coding interview question.
• Optimization problems: Used in “binary search on answer” problems.

Prerequisites

1. Sorted data: The array must be sorted (ascending or descending).
2. Random access: Any element can be accessed in O(1) time (arrays qualify).
3. Monotonic property: The search space must be monotonic.

How Binary Search Works

For a sorted array and target x:

1. Find the middle index mid.
2. If arr[mid] == x, return mid.
3. If arr[mid] < x, search the right half.
4. If arr[mid] > x, search the left half.
5. Repeat until found or search space is empty.

Example:

text

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Target: 23 Step 1: mid = 4, arr[4] = 16 < 23 → search right [23, 38, 56, 72, 91] Step 2: mid = 7, arr[7] = 56 > 23 → search left [23, 38] Step 3: mid = 5, arr[5] = 23 == 23 → Found at index 5

Complexity Analysis

Space:

• Iterative: O(1)
• Recursive: O(log n) (call stack)

Syntax & Core Mechanics

Iterative Binary Search

c

#include <stdio.h> int binarySearchIterative(const int arr[], int n, int target) { int low = 0; int high = n - 1; while (low <= high) { /* Avoid overflow: low + (high - low) / 2 */ int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } if (arr[mid] < target) { low = mid + 1; /* Search right half */ } else { high = mid - 1; /* Search left half */ } } return -1; /* Not found */ } int main(void) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr) / sizeof(arr[0]); int target = 10; int result = binarySearchIterative(arr, n, target); if (result == -1) { printf("Element is not present in array\n"); } else { printf("Element is present at index %d\n", result); } return 0; }

Expected output:

text

Element is present at index 3

Time: O(log n), Space: O(1)

Recursive Binary Search

c

#include <stdio.h> int binarySearchRecursive(const int arr[], int low, int high, int target) { if (low > high) { return -1; /* Not found */ } int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } if (arr[mid] > target) { return binarySearchRecursive(arr, low, mid - 1, target); } return binarySearchRecursive(arr, mid + 1, high, target); } int main(void) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr) / sizeof(arr[0]); int target = 10; int result = binarySearchRecursive(arr, 0, n - 1, target); if (result == -1) { printf("Element is not present in array\n"); } else { printf("Element is present at index %d\n", result); } return 0; }

Expected output:

text

Element is present at index 3

Time: O(log n), Space: O(log n) due to recursion stack

Finding First and Last Occurrence

For arrays with duplicates, binary search can be modified to find first/last occurrence.

c

/* Find first occurrence of target */ int findFirst(const int arr[], int n, int target) { int low = 0, high = n - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; high = mid - 1; /* Search left for earlier occurrence */ } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } /* Find last occurrence of target */ int findLast(const int arr[], int n, int target) { int low = 0, high = n - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; low = mid + 1; /* Search right for later occurrence */ } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; }

Full Practical Code Example with Explanation

This program demonstrates all binary search variants with verification, performance comparison, and edge cases.

Program: Binary Search Complete Demo

c

/** * binary_search_demo.c * Demonstrates iterative, recursive, and variant binary search approaches. * Includes first/last occurrence, verification, and edge cases. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int binarySearchIterative(const int arr[], int n, int target); int binarySearchRecursive(const int arr[], int low, int high, int target); int findFirstOccurrence(const int arr[], int n, int target); int findLastOccurrence(const int arr[], int n, int target); int findClosest(const int arr[], int n, int target); int binarySearchDescending(const int arr[], int n, int target); int compareInts(const void *a, const void *b); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Binary Search Complete Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Variants\n"); printf("2. Search in Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n, target; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements (will be sorted):\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } qsort(arr, n, sizeof(int), compareInts); printf("\nSorted array: "); printArray(arr, n); if (readInteger("Enter target: ", &target) != 0) { fprintf(stderr, "Invalid target.\n"); break; } int iter = binarySearchIterative(arr, n, target); int rec = binarySearchRecursive(arr, 0, n - 1, target); int first = findFirstOccurrence(arr, n, target); int last = findLastOccurrence(arr, n, target); printf("Iterative: %d\n", iter); printf("Recursive: %d\n", rec); printf("First occurrence: %d\n", first); printf("Last occurrence: %d\n", last); if (iter != -1) { printf("Verification: %s\n", (iter == rec && iter == first) ? "PASS" : "FAIL"); } break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Iterative binary search */ int binarySearchIterative(const int arr[], int n, int target) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) low = mid + 1; else high = mid - 1; } return -1; } /* Recursive binary search */ int binarySearchRecursive(const int arr[], int low, int high, int target) { if (low > high) return -1; int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; if (arr[mid] > target) return binarySearchRecursive(arr, low, mid - 1, target); return binarySearchRecursive(arr, mid + 1, high, target); } /* Find first occurrence */ int findFirstOccurrence(const int arr[], int n, int target) { int low = 0, high = n - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; high = mid - 1; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } /* Find last occurrence */ int findLastOccurrence(const int arr[], int n, int target) { int low = 0, high = n - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; low = mid + 1; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } /* Find closest element to target */ int findClosest(const int arr[], int n, int target) { if (n <= 0) return -1; int low = 0, high = n - 1; if (target <= arr[0]) return 0; if (target >= arr[n - 1]) return n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) { if (mid + 1 < n && arr[mid + 1] > target) { return (target - arr[mid] < arr[mid + 1] - target) ? mid : mid + 1; } low = mid + 1; } else { if (mid - 1 >= 0 && arr[mid - 1] < target) { return (target - arr[mid - 1] < arr[mid] - target) ? mid - 1 : mid; } high = mid - 1; } } return -1; } /* Binary search for descending sorted array */ int binarySearchDescending(const int arr[], int n, int target) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; if (arr[mid] > target) low = mid + 1; else high = mid - 1; } return -1; } /* Comparison function */ int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demonstrates all variants */ void demonstrateApproaches(void) { printf("\n=== Binary Search Variants ===\n"); int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; int n = sizeof(arr) / sizeof(arr[0]); printf("\nArray: "); printArray(arr, n); int targets[] = {2, 23, 91, 100}; int numTargets = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < numTargets; i++) { int t = targets[i]; printf("\nTarget %d:\n", t); printf(" Iterative: %d\n", binarySearchIterative(arr, n, t)); printf(" Recursive: %d\n", binarySearchRecursive(arr, 0, n - 1, t)); printf(" Closest: %d\n", findClosest(arr, n, t)); } /* First/last occurrence with duplicates */ int dupArr[] = {1, 2, 2, 2, 3, 4, 5}; int dupN = sizeof(dupArr) / sizeof(dupArr[0]); printf("\nArray with duplicates: "); printArray(dupArr, dupN); printf("Target 2:\n"); printf(" First: %d\n", findFirstOccurrence(dupArr, dupN, 2)); printf(" Last: %d\n", findLastOccurrence(dupArr, dupN, 2)); /* Descending array */ int descArr[] = {100, 90, 80, 70, 60, 50}; int descN = sizeof(descArr) / sizeof(descArr[0]); printf("\nDescending array: "); printArray(descArr, descN); printf("Target 70:\n"); printf(" Index: %d\n", binarySearchDescending(descArr, descN, 70)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 10000000) ===\n"); int n = 10000000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } for (int i = 0; i < n; i++) { arr[i] = i * 2; } int target = arr[n - 1]; /* Worst case: last element */ clock_t start, end; double timeTaken; /* Linear search for comparison */ start = clock(); int linearResult = -1; for (int i = 0; i < n; i++) { if (arr[i] == target) { linearResult = i; break; } } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Linear search (O(n)): Result = %d, Time = %.3f ms\n", linearResult, timeTaken); /* Binary search */ start = clock(); int binResult = binarySearchIterative(arr, n, target); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Binary search (O(log n)): Result = %d, Time = %.3f ms\n", binResult, timeTaken); printf("\nVerification: %s\n", (linearResult == binResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Empty array */ int arr1[] = {}; printf("Case 1: Empty array\n"); printf(" Result: %d\n", binarySearchIterative(arr1, 0, 5)); /* Case 2: Single element, found */ int arr2[] = {42}; printf("\nCase 2: Single element, found\n"); printf(" Array: "); printArray(arr2, 1); printf(" Result: %d\n", binarySearchIterative(arr2, 1, 42)); /* Case 3: Single element, not found */ int arr3[] = {42}; printf("\nCase 3: Single element, not found\n"); printf(" Array: "); printArray(arr3, 1); printf(" Result: %d\n", binarySearchIterative(arr3, 1, 10)); /* Case 4: Target at start */ int arr4[] = {1, 2, 3, 4, 5}; printf("\nCase 4: Target at start\n"); printf(" Array: "); printArray(arr4, 5); printf(" Result: %d\n", binarySearchIterative(arr4, 5, 1)); /* Case 5: Target at end */ int arr5[] = {1, 2, 3, 4, 5}; printf("\nCase 5: Target at end\n"); printf(" Array: "); printArray(arr5, 5); printf(" Result: %d\n", binarySearchIterative(arr5, 5, 5)); /* Case 6: All same elements */ int arr6[] = {5, 5, 5, 5, 5}; printf("\nCase 6: All same elements\n"); printf(" Array: "); printArray(arr6, 5); printf(" First: %d, Last: %d\n", findFirstOccurrence(arr6, 5, 5), findLastOccurrence(arr6, 5, 5)); /* Case 7: Negative numbers */ int arr7[] = {-10, -5, 0, 5, 10}; printf("\nCase 7: Negative numbers\n"); printf(" Array: "); printArray(arr7, 5); printf(" Target -5: %d\n", binarySearchIterative(arr7, 5, -5)); /* Case 8: Large array overflow check */ int arr8[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; printf("\nCase 8: Overflow-safe mid calculation\n"); printf(" Array: "); printArray(arr8, 10); printf(" Target 56: %d\n", binarySearchIterative(arr8, 10, 56)); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Binary Search Variants

1. Iterative: Standard while loop; O(log n) time, O(1) space.
2. Recursive: Self-calling function; O(log n) time, O(log n) space.
3. First Occurrence: Modified to find leftmost match.
4. Last Occurrence: Modified to find rightmost match.
5. Closest: Finds nearest element to target.
6. Descending: Adapted for descending arrays.

Expected Output (sample run)

text

=== Binary Search Complete Demo === --- Menu --- 1. Demonstrate All Variants 2. Search in Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Binary Search Variants === Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Target 2: Iterative: 0 Recursive: 0 Closest: 0 Target 23: Iterative: 5 Recursive: 5 Closest: 5 Target 91: Iterative: 9 Recursive: 9 Closest: 9 Target 100: Iterative: -1 Recursive: -1 Closest: 9 Array with duplicates: [1, 2, 2, 2, 3, 4, 5] Target 2: First: 1 Last: 3 Descending array: [100, 90, 80, 70, 60, 50] Target 70: Index: 3 --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 10000000) === Linear search (O(n)): Result = 9999999, Time = 45.234 ms Binary search (O(log n)): Result = 9999999, Time = 0.002 ms Verification: PASS --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Empty array Result: -1 Case 2: Single element, found Array: [42] Result: 0 Case 3: Single element, not found Array: [42] Result: -1 Case 4: Target at start Array: [1, 2, 3, 4, 5] Result: 0 Case 5: Target at end Array: [1, 2, 3, 4, 5] Result: 4 Case 6: All same elements Array: [5, 5, 5, 5, 5] First: 0, Last: 4 Case 7: Negative numbers Array: [-10, -5, 0, 5, 10] Target -5: 1 Case 8: Overflow-safe mid calculation Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Target 56: 7

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow in Mid Calculation

(low + high) / 2 can overflow for large arrays.

c

int mid = (low + high) / 2; /* BUG: potential overflow */ int mid = low + (high - low) / 2; /* Correct */

2. Infinite Loop from Wrong Update

Forgetting to update low or high causes infinite loops.

c

if (arr[mid] < target) low = mid; /* BUG: no progress */ if (arr[mid] < target) low = mid + 1; /* Correct */

3. Off-by-One in Loop Condition

Using low < high vs low <= high affects termination.

c

while (low <= high) { ... } /* Correct for standard binary search */

4. Unsorted Array

Binary search requires a sorted array; results are undefined otherwise.

Solution: Sort the array first with qsort.

5. Empty Array

Return -1 for empty arrays.

c

if (n <= 0) return -1;

6. Duplicates

Standard binary search returns any occurrence; use variants for first/last.

7. Recursion Depth

Recursive binary search uses O(log n) stack space — safe for typical arrays.

8. Descending Arrays

Adapt comparison logic for descending order.

c

if (arr[mid] > target) low = mid + 1; else high = mid - 1;

9. Search on Monotonic Functions

Binary search works on any monotonic search space, not just arrays.

10. Memory Considerations

• Iterative: O(1) extra space.
• Recursive: O(log n) stack space.
• No dynamic allocation required.
• Use int for indices; size_t for very large arrays.

Summary & Best Practices

Binary Search is a fundamental O(log n) algorithm for searching in sorted arrays. It is widely applicable and forms the foundation for many advanced algorithms.

Key Takeaways

• Requires sorted data and random access.
• Iterative: O(log n) time, O(1) space.
• Recursive: O(log n) time, O(log n) space.
• Use low + (high - low) / 2 to avoid overflow.
• Variants: first/last occurrence, closest match, descending.
• Applications: databases, debugging, routing, ML tuning.

Best Practices

1. Use the iterative version for O(1) space.
2. Use low + (high - low) / 2 to prevent overflow.
3. Ensure the array is sorted before searching.
4. Update low = mid + 1 or high = mid - 1 for progress.
5. Handle edge cases: empty, single element, target not found.
6. Use variants for first/last occurrence when duplicates exist.
7. Use qsort for sorting before binary search.
8. Test with negative numbers and boundary targets.
9. Consider binary search on answer for optimization problems.
10. Profile for large arrays.

By mastering Binary Search, you’ll have a powerful tool for efficient searching and be prepared for advanced algorithms and data structures.