Binary Search Applications in C: A Comprehensive Tutorial

Binary search is one of the most powerful algorithmic techniques in computer science. Beyond simple searching, it powers a wide range of problems—from mathematical computations to optimization and rotated array searching. This tutorial covers seven important binary search applications in C, each with complete, portable implementations.

The seven topics are:

1. Square Root of an Integer
2. First and Last Positions in a Sorted Array
3. Count 1’s in a Sorted Binary Array
4. Unbounded Binary Search
5. Minimum in a Sorted Rotated Array
6. Search in a Sorted Rotated Array
7. Aggressive Cows (Optimization Problem)

Conceptual Introduction & Fundamentals

The Binary Search Template

All binary search variants share a common structure:

c

int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; /* Overflow-safe */ if (condition(mid)) { /* Narrow search to one half */ } else { /* Narrow search to other half */ } } return answer;

Key Prerequisites

Applications Overview

Syntax & Core Mechanics

1. Square Root of an Integer

Problem: Find the integer square root of n (floor of √n) without using built-in sqrt().

Idea: Binary search on the answer [0, n]. Find the largest x such that x² ≤ n.

c

#include <stdio.h> long long integerSqrt(long long n) { if (n < 0) return -1; /* Undefined for negatives */ if (n == 0 || n == 1) return n; long long low = 1, high = n, result = 1; while (low <= high) { long long mid = low + (high - low) / 2; /* Avoid overflow: use division instead of mid*mid */ if (mid <= n / mid) { result = mid; low = mid + 1; /* Try larger */ } else { high = mid - 1; } } return result; } int main(void) { long long tests[] = {0, 1, 4, 8, 16, 25, 100, 999999999}; int count = sizeof(tests) / sizeof(tests[0]); for (int i = 0; i < count; i++) { printf("sqrt(%lld) = %lld\n", tests[i], integerSqrt(tests[i])); } return 0; }

Expected output:

text

sqrt(0) = 0 sqrt(1) = 1 sqrt(4) = 2 sqrt(8) = 2 sqrt(16) = 4 sqrt(25) = 5 sqrt(100) = 10 sqrt(999999999) = 31622

Key insight: Use mid <= n / mid instead of mid * mid <= n to avoid overflow.

2. First and Last Positions in a Sorted Array

Problem: Find the first and last occurrence of a target in a sorted array (with duplicates).

Idea: Two modified binary searches — one biased left (first), one biased right (last).

c

#include <stdio.h> int findFirst(const int arr[], int n, int target) { int low = 0, high = n - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; high = mid - 1; /* Bias left */ } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } int findLast(const int arr[], int n, int target) { int low = 0, high = n - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { result = mid; low = mid + 1; /* Bias right */ } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return result; } int main(void) { int arr[] = {1, 2, 2, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int target = 2; int first = findFirst(arr, n, target); int last = findLast(arr, n, target); if (first == -1) { printf("%d not found\n", target); } else { printf("First occurrence of %d: %d\n", target, first); printf("Last occurrence of %d: %d\n", target, last); printf("Count: %d\n", last - first + 1); } return 0; }

Expected output:

text

First occurrence of 2: 1 Last occurrence of 2: 3 Count: 3

3. Count 1’s in a Sorted Binary Array

Problem: Count the number of 1’s in a sorted array containing only 0’s and 1’s.

Idea: Find the first occurrence of 1. Count = n - firstOneIndex.

c

#include <stdio.h> int countOnes(const int arr[], int n) { int low = 0, high = n - 1, firstOne = n; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == 1) { firstOne = mid; high = mid - 1; /* Search left for earlier 1 */ } else { low = mid + 1; /* 0: search right */ } } return n - firstOne; } int main(void) { int arr1[] = {0, 0, 0, 1, 1, 1, 1}; int arr2[] = {0, 0, 0, 0}; int arr3[] = {1, 1, 1, 1}; int arr4[] = {0}; printf("Test 1: %d\n", countOnes(arr1, 7)); printf("Test 2: %d\n", countOnes(arr2, 4)); printf("Test 3: %d\n", countOnes(arr3, 4)); printf("Test 4: %d\n", countOnes(arr4, 1)); return 0; }

Expected output:

text

Test 1: 4 Test 2: 0 Test 3: 4 Test 4: 0

4. Unbounded Binary Search

Problem: Search for a target in an array of infinite size (or unknown size), where all elements are sorted.

Idea: Double the index high until arr[high] >= target, then perform standard binary search.

c

#include <stdio.h> /* Simulated infinite array via a function */ int getValue(int idx) { static int data[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}; int size = sizeof(data) / sizeof(data[0]); if (idx >= size) return 1000000; /* Sentinel */ return data[idx]; } int unboundedSearch(int target) { if (getValue(0) == target) return 0; int high = 1; while (getValue(high) < target) { if (high > 1000000) return -1; /* Safety bound */ high *= 2; } int low = high / 2; while (low <= high) { int mid = low + (high - low) / 2; int val = getValue(mid); if (val == target) return mid; if (val < target) low = mid + 1; else high = mid - 1; } return -1; } int main(void) { int targets[] = {1, 9, 29, 30}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int result = unboundedSearch(targets[i]); if (result == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], result); } return 0; }

Expected output:

text

Target 1: Index 0 Target 9: Index 4 Target 29: Index 14 Target 30: Not found

5. Minimum in a Sorted Rotated Array

Problem: Find the minimum element in a sorted array rotated at an unknown pivot.

Idea: Compare arr[mid] with arr[high]; narrow the search.

c

#include <stdio.h> int findMinRotated(const int arr[], int n) { if (n <= 0) return -1; int low = 0, high = n - 1; while (low < high) { /* If the range is already sorted, minimum is at low */ if (arr[low] < arr[high]) return arr[low]; int mid = low + (high - low) / 2; if (arr[mid] > arr[high]) { low = mid + 1; /* Minimum in right half */ } else { high = mid; /* Minimum at mid or left half */ } } return arr[low]; } int main(void) { int arr1[] = {5, 6, 1, 2, 3, 4}; int arr2[] = {3, 1, 2}; int arr3[] = {4, 2, 3}; int arr4[] = {1, 2, 3, 4}; printf("Min 1: %d\n", findMinRotated(arr1, 6)); printf("Min 2: %d\n", findMinRotated(arr2, 3)); printf("Min 3: %d\n", findMinRotated(arr3, 3)); printf("Min 4: %d\n", findMinRotated(arr4, 4)); return 0; }

Expected output:

text

Min 1: 1 Min 2: 1 Min 3: 2 Min 4: 1

6. Search in a Sorted Rotated Array

Problem: Search for a target in a sorted rotated array.

Idea: One half is always sorted. Determine which half and search accordingly.

c

#include <stdio.h> int searchRotated(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; /* Left half is sorted */ if (arr[low] <= arr[mid]) { if (target >= arr[low] && target < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } /* Right half is sorted */ else { if (target > arr[mid] && target <= arr[high]) { low = mid + 1; } else { high = mid - 1; } } } return -1; } int main(void) { int arr[] = {5, 6, 7, 8, 9, 1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); int targets[] = {5, 1, 3, 8, 10, 0}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int result = searchRotated(arr, n, targets[i]); if (result == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], result); } return 0; }

Expected output:

text

Target 5: Index 0 Target 1: Index 5 Target 3: Index 7 Target 8: Index 3 Target 10: Not found Target 0: Not found

7. Aggressive Cows (Optimization)

Problem: Place k cows in n stalls (given positions) so that the minimum distance between any two cows is maximized.

Idea: Binary search on the answer (distance). For each candidate distance, check if k cows can be placed with at least that gap.

c

#include <stdio.h> #include <stdlib.h> 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); } /* Check if k cows can be placed with minimum distance >= dist */ int canPlace(const int stalls[], int n, int k, int dist) { int count = 1; /* Place first cow at stalls[0] */ int lastPos = stalls[0]; for (int i = 1; i < n; i++) { if (stalls[i] - lastPos >= dist) { count++; lastPos = stalls[i]; if (count >= k) return 1; } } return 0; } int aggressiveCows(int stalls[], int n, int k) { if (k > n) return -1; qsort(stalls, n, sizeof(int), compareInts); int low = 1; int high = stalls[n - 1] - stalls[0]; int result = 0; while (low <= high) { int mid = low + (high - low) / 2; if (canPlace(stalls, n, k, mid)) { result = mid; /* Try larger distance */ low = mid + 1; } else { high = mid - 1; /* Try smaller distance */ } } return result; } int main(void) { int stalls1[] = {1, 2, 4, 8, 9}; int stalls2[] = {1, 2, 3, 4, 5}; printf("Aggressive Cows (k=3, stalls=[1,2,4,8,9]): %d\n", aggressiveCows(stalls1, 5, 3)); printf("Aggressive Cows (k=3, stalls=[1,2,3,4,5]): %d\n", aggressiveCows(stalls2, 5, 3)); printf("Aggressive Cows (k=2, stalls=[1,2,4,8,9]): %d\n", aggressiveCows(stalls1, 5, 2)); return 0; }

Expected output:

text

Aggressive Cows (k=3, stalls=[1,2,4,8,9]): 3 Aggressive Cows (k=3, stalls=[1,2,3,4,5]): 2 Aggressive Cows (k=2, stalls=[1,2,4,8,9]): 8

Full Practical Code Example with Explanation

This program combines all seven binary search applications into a single interactive tool.

c

/** * binary_search_applications.c * Demonstrates seven binary search applications in C. * Covers sqrt, first/last occurrence, count 1's, unbounded search, * rotated array min/search, and aggressive cows. */ #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 */ long long integerSqrt(long long n); int findFirst(const int arr[], int n, int target); int findLast(const int arr[], int n, int target); int countOnes(const int arr[], int n); int unboundedSearch(int target); int findMinRotated(const int arr[], int n); int searchRotated(const int arr[], int n, int target); int aggressiveCows(int stalls[], int n, int k); int compareInts(const void *a, const void *b); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demoSquareRoot(void); void demoFirstLast(void); void demoCountOnes(void); void demoUnbounded(void); void demoRotatedMin(void); void demoRotatedSearch(void); void demoAggressiveCows(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Binary Search Applications Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Square Root of Integer\n"); printf("2. First and Last Position\n"); printf("3. Count 1's in Binary Array\n"); printf("4. Unbounded Binary Search\n"); printf("5. Minimum in Rotated Array\n"); printf("6. Search in Rotated Array\n"); printf("7. Aggressive Cows\n"); printf("8. 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: demoSquareRoot(); break; case 2: demoFirstLast(); break; case 3: demoCountOnes(); break; case 4: demoUnbounded(); break; case 5: demoRotatedMin(); break; case 6: demoRotatedSearch(); break; case 7: demoAggressiveCows(); break; case 8: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* 1. Integer square root */ long long integerSqrt(long long n) { if (n < 0) return -1; if (n == 0 || n == 1) return n; long long low = 1, high = n, result = 1; while (low <= high) { long long mid = low + (high - low) / 2; if (mid <= n / mid) { result = mid; low = mid + 1; } else { high = mid - 1; } } return result; } /* 2. First occurrence */ int findFirst(const int arr[], int n, int target) { int low = 0, high = n - 1, 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; } /* 2. Last occurrence */ int findLast(const int arr[], int n, int target) { int low = 0, high = n - 1, 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; } /* 3. Count 1's */ int countOnes(const int arr[], int n) { int low = 0, high = n - 1, firstOne = n; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == 1) { firstOne = mid; high = mid - 1; } else { low = mid + 1; } } return n - firstOne; } /* 4. Unbounded search */ int getValue(int idx) { static int data[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}; int size = sizeof(data) / sizeof(data[0]); if (idx < 0 || idx >= size) return 1000000; return data[idx]; } int unboundedSearch(int target) { if (getValue(0) == target) return 0; int high = 1; while (getValue(high) < target) { if (high > 1000000) return -1; high *= 2; } int low = high / 2; while (low <= high) { int mid = low + (high - low) / 2; int val = getValue(mid); if (val == target) return mid; if (val < target) low = mid + 1; else high = mid - 1; } return -1; } /* 5. Minimum in rotated array */ int findMinRotated(const int arr[], int n) { if (n <= 0) return -1; int low = 0, high = n - 1; while (low < high) { if (arr[low] < arr[high]) return arr[low]; int mid = low + (high - low) / 2; if (arr[mid] > arr[high]) low = mid + 1; else high = mid; } return arr[low]; } /* 6. Search in rotated array */ int searchRotated(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[low] <= arr[mid]) { if (target >= arr[low] && target < arr[mid]) high = mid - 1; else low = mid + 1; } else { if (target > arr[mid] && target <= arr[high]) low = mid + 1; else high = mid - 1; } } return -1; } /* 7. Aggressive Cows */ 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); } int canPlace(const int stalls[], int n, int k, int dist) { int count = 1; int lastPos = stalls[0]; for (int i = 1; i < n; i++) { if (stalls[i] - lastPos >= dist) { count++; lastPos = stalls[i]; if (count >= k) return 1; } } return 0; } int aggressiveCows(int stalls[], int n, int k) { if (k > n) return -1; qsort(stalls, n, sizeof(int), compareInts); int low = 1; int high = stalls[n - 1] - stalls[0]; int result = 0; while (low <= high) { int mid = low + (high - low) / 2; if (canPlace(stalls, n, k, mid)) { result = mid; low = mid + 1; } else { high = mid - 1; } } return result; } /* Print 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"); } /* Demos */ void demoSquareRoot(void) { printf("\n=== Integer Square Root ===\n"); long long tests[] = {0, 1, 4, 8, 16, 25, 100, 999999999}; int count = sizeof(tests) / sizeof(tests[0]); for (int i = 0; i < count; i++) { printf("sqrt(%lld) = %lld\n", tests[i], integerSqrt(tests[i])); } } void demoFirstLast(void) { printf("\n=== First and Last Position ===\n"); int arr[] = {1, 2, 2, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("Array: "); printArray(arr, n); int target = 2; int first = findFirst(arr, n, target); int last = findLast(arr, n, target); if (first == -1) printf("%d not found\n", target); else printf("First: %d, Last: %d, Count: %d\n", first, last, last - first + 1); } void demoCountOnes(void) { printf("\n=== Count 1's in Sorted Binary Array ===\n"); int arr1[] = {0, 0, 0, 1, 1, 1, 1}; int arr2[] = {0, 0, 0, 0}; int arr3[] = {1, 1, 1, 1}; printf("arr1: "); printArray(arr1, 7); printf(" Count 1's: %d\n", countOnes(arr1, 7)); printf("arr2: "); printArray(arr2, 4); printf(" Count 1's: %d\n", countOnes(arr2, 4)); printf("arr3: "); printArray(arr3, 4); printf(" Count 1's: %d\n", countOnes(arr3, 4)); } void demoUnbounded(void) { printf("\n=== Unbounded Binary Search ===\n"); int targets[] = {1, 9, 29, 30}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int r = unboundedSearch(targets[i]); if (r == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], r); } } void demoRotatedMin(void) { printf("\n=== Minimum in Sorted Rotated Array ===\n"); int arr1[] = {5, 6, 1, 2, 3, 4}; int arr2[] = {3, 1, 2}; int arr3[] = {4, 2, 3}; int arr4[] = {1, 2, 3, 4}; printf("arr1: "); printArray(arr1, 6); printf(" Min: %d\n", findMinRotated(arr1, 6)); printf("arr2: "); printArray(arr2, 3); printf(" Min: %d\n", findMinRotated(arr2, 3)); printf("arr3: "); printArray(arr3, 3); printf(" Min: %d\n", findMinRotated(arr3, 3)); printf("arr4: "); printArray(arr4, 4); printf(" Min: %d\n", findMinRotated(arr4, 4)); } void demoRotatedSearch(void) { printf("\n=== Search in Sorted Rotated Array ===\n"); int arr[] = {5, 6, 7, 8, 9, 1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Array: "); printArray(arr, n); int targets[] = {5, 1, 3, 8, 10, 0}; int count = sizeof(targets) / sizeof(targets[0]); for (int i = 0; i < count; i++) { int r = searchRotated(arr, n, targets[i]); if (r == -1) printf("Target %d: Not found\n", targets[i]); else printf("Target %d: Index %d\n", targets[i], r); } } void demoAggressiveCows(void) { printf("\n=== Aggressive Cows ===\n"); int stalls1[] = {1, 2, 4, 8, 9}; int stalls2[] = {1, 2, 3, 4, 5}; printf("stalls=[1,2,4,8,9], k=3 → %d\n", aggressiveCows(stalls1, 5, 3)); printf("stalls=[1,2,3,4,5], k=3 → %d\n", aggressiveCows(stalls2, 5, 3)); printf("stalls=[1,2,4,8,9], k=2 → %d\n", aggressiveCows(stalls1, 5, 2)); } /* Read 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; }

Expected Output (sample run)

text

=== Binary Search Applications Demo === --- Menu --- 1. Square Root of Integer 2. First and Last Position 3. Count 1's in Binary Array 4. Unbounded Binary Search 5. Minimum in Rotated Array 6. Search in Rotated Array 7. Aggressive Cows 8. Exit Enter choice: 1 === Integer Square Root === sqrt(0) = 0 sqrt(1) = 1 sqrt(4) = 2 sqrt(8) = 2 sqrt(16) = 4 sqrt(25) = 5 sqrt(100) = 10 sqrt(999999999) = 31622

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow in mid * mid

Use mid <= n / mid instead of mid * mid <= n.

2. Infinite Loops from Non-Progress

Always update low = mid + 1 or high = mid - 1.

3. Off-by-One in Rotated Arrays

Use high = mid (not mid - 1) when arr[mid] < arr[high] to keep minimum in range.

4. Missing Check for Sorted Subarray

In rotated search, always check which half is sorted first.

5. Unbounded Search Safety

Include an upper bound to prevent infinite doubling.

6. Aggressive Cows: Sorting Required

Always sort stall positions first.

7. First/Last Occurrence Initialization

Initialize result = -1 and update only on match.

8. Empty Arrays

Return sentinel values (-1) for empty inputs.

9. Duplicates in Rotated Arrays

The minimum in rotated array with duplicates can be ambiguous; linear fallback may be needed.

10. Memory Considerations

• All seven algorithms use O(1) extra space.
• No dynamic allocation required.
• Use long long for integer sqrt to avoid overflow.

Summary & Best Practices

Binary search is a versatile technique that extends far beyond simple searching. The seven applications in this tutorial demonstrate its power across mathematical, structural, and optimization problems.

Key Takeaways

Best Practices

1. Use low + (high - low) / 2 to avoid overflow.
2. Ensure monotonicity before applying binary search.
3. Check both halves’ sorted status in rotated arrays.
4. Bias first/last occurrence searches appropriately.
5. Include safety bounds in unbounded search.
6. Sort input for aggressive cows.
7. Use long long for large computations (square root).
8. Handle edge cases: empty, single element, duplicates.
9. Verify with brute force during testing.
10. Profile for large inputs.

By mastering these seven applications, you’ll be well-equipped to solve a wide range of binary search problems in competitive programming and technical interviews.