Tag time complexity

Zeros Count in Sorted Binary Array: A Comprehensive Tutorial

Counting zeros in a sorted binary array is a classic algorithmic problem that demonstrates efficient searching techniques. A sorted binary array contains only 0s and 1s, with all 0s appearing before all 1s (or vice versa). Finding the count of zeros efficiently is essential for understanding binary search, time complexity analysis, and optimization techniques.

This tutorial provides an in-depth exploration of counting zeros in a sorted binary array: problem understanding, naive and optimized approaches, binary search implementation, edge cases, and best practices.

Conceptual Introduction & Fundamentals

What is a Sorted Binary Array?

A sorted binary array is an array that contains only two distinct values: 0 and 1. The array is sorted, meaning all 0s come first, followed by all 1s (ascending order). For example:

text

[0, 0, 0, 1, 1, 1] // Three zeros followed by three ones [0, 0, 0, 0] // All zeros [1, 1, 1, 1] // All ones [] // Empty array

Problem Statement

Given a sorted binary array (all 0s followed by all 1s), count the number of zeros in the array.

Examples:

• Input: [0, 0, 0, 1, 1] → Output: 3
• Input: [0, 0, 0, 0] → Output: 4
• Input: [1, 1, 1, 1] → Output: 0
• Input: [] → Output: 0

Why This Problem Matters

• Algorithm design: Demonstrates linear search vs. binary search trade-offs.
• Time complexity analysis: O(n) vs. O(log n) comparison.
• Foundation for advanced problems: Variations include finding first occurrence, last occurrence, and count of any element in sorted arrays.
• Interview preparation: Common coding interview question.
• Real-world applications: Counting occurrences in sorted datasets, database queries, and data analysis.

Approaches Overview

Syntax & Core Mechanics

Approach 1: Linear Scan (Naive)

Traverse the array from left to right, counting zeros until a 1 is encountered.

c

#include <stdio.h> int countZerosLinear(const int arr[], int n) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] == 0) { count++; } else { break; // Since sorted, first 1 means no more zeros } } return count; } int main(void) { int arr[] = {0, 0, 0, 1, 1, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("Zeros: %d\n", countZerosLinear(arr, n)); return 0; }

Expected output:

text

Zeros: 3

Time complexity: O(n) in worst case (all zeros).

Approach 2: Binary Search (Find First 1)

Since the array is sorted, use binary search to find the index of the first 1. The count of zeros equals that index.

c

#include <stdio.h> int countZerosBinary(const int arr[], int n) { int left = 0; int right = n - 1; int firstOneIndex = n; // Default: no 1 found while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == 1) { firstOneIndex = mid; // Record position right = mid - 1; // Search left half } else { left = mid + 1; // Search right half } } return firstOneIndex; // Number of zeros = index of first 1 } int main(void) { int arr[] = {0, 0, 0, 1, 1, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("Zeros: %d\n", countZerosBinary(arr, n)); return 0; }

Expected output:

text

Zeros: 3

Time complexity: O(log n).

Binary Search Logic Explained

1. Initialize left = 0, right = n - 1, firstOneIndex = n.
2. While left <= right:
   • Calculate mid = left + (right - left) / 2 (avoids overflow).
   • If arr[mid] == 1, update firstOneIndex = mid and search left half (right = mid - 1).
   • If arr[mid] == 0, search right half (left = mid + 1).
3. After loop, firstOneIndex is the index of the first 1.
4. The count of zeros equals firstOneIndex.

Approach 3: Binary Search (Find Last 0)

Alternatively, find the index of the last 0. The count of zeros equals lastZeroIndex + 1.

c

#include <stdio.h> int countZerosLastZero(const int arr[], int n) { int left = 0; int right = n - 1; int lastZeroIndex = -1; // Default: no 0 found while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == 0) { lastZeroIndex = mid; // Record position left = mid + 1; // Search right half } else { right = mid - 1; // Search left half } } return lastZeroIndex + 1; // Count of zeros } int main(void) { int arr[] = {0, 0, 0, 1, 1, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("Zeros: %d\n", countZerosLastZero(arr, n)); return 0; }

Expected output:

text

Zeros: 3

Handling Edge Cases

c

#include <stdio.h> int countZerosEdge(const int arr[], int n) { /* Empty array */ if (n == 0) return 0; /* All ones: first element is 1 */ if (arr[0] == 1) return 0; /* All zeros: last element is 0 */ if (arr[n - 1] == 0) return n; /* Mixed: binary search */ int left = 0; int right = n - 1; int firstOneIndex = n; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == 1) { firstOneIndex = mid; right = mid - 1; } else { left = mid + 1; } } return firstOneIndex; }

Full Practical Code Example with Explanation

This program demonstrates multiple approaches to count zeros in a sorted binary array, including linear scan, binary search, and recursive binary search, with performance comparison.

Program: Zero Counter for Sorted Binary Arrays

c

/** * count_zeros_sorted_binary.c * Counts zeros in a sorted binary array using multiple approaches. * Demonstrates linear scan, iterative binary search, and recursive binary search. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <errno.h> #define MAX_LINE_LEN 100 /* Function prototypes */ int countZerosLinear(const int arr[], int n); int countZerosBinary(const int arr[], int n); int countZerosRecursive(const int arr[], int left, int right); int countZerosWrapper(const int arr[], int n); int readInteger(const char *prompt, int *outValue); void demonstrateApproach(const char *name, int result, clock_t start, clock_t end); void printArray(const int arr[], int n); int main(void) { int choice; char buffer[MAX_LINE_LEN]; /* Test arrays */ int arr1[] = {0, 0, 0, 1, 1, 1}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int arr2[] = {0, 0, 0, 0, 0}; int n2 = sizeof(arr2) / sizeof(arr2[0]); int arr3[] = {1, 1, 1, 1}; int n3 = sizeof(arr3) / sizeof(arr3[0]); int arr4[] = {}; int n4 = 0; int arr5[] = {0}; int n5 = sizeof(arr5) / sizeof(arr5[0]); printf("=== Zero Counter for Sorted Binary Arrays ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. 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: printf("\n=== Sample Arrays ===\n"); printf("\nArray 1: "); printArray(arr1, n1); printf("Zeros (linear): %d\n", countZerosLinear(arr1, n1)); printf("Zeros (binary): %d\n", countZerosBinary(arr1, n1)); printf("Zeros (recursive): %d\n", countZerosWrapper(arr1, n1)); printf("\nArray 2 (all zeros): "); printArray(arr2, n2); printf("Zeros (linear): %d\n", countZerosLinear(arr2, n2)); printf("Zeros (binary): %d\n", countZerosBinary(arr2, n2)); printf("Zeros (recursive): %d\n", countZerosWrapper(arr2, n2)); printf("\nArray 3 (all ones): "); printArray(arr3, n3); printf("Zeros (linear): %d\n", countZerosLinear(arr3, n3)); printf("Zeros (binary): %d\n", countZerosBinary(arr3, n3)); printf("Zeros (recursive): %d\n", countZerosWrapper(arr3, n3)); printf("\nArray 4 (empty): "); printArray(arr4, n4); printf("Zeros (linear): %d\n", countZerosLinear(arr4, n4)); printf("Zeros (binary): %d\n", countZerosBinary(arr4, n4)); printf("Zeros (recursive): %d\n", countZerosWrapper(arr4, n4)); printf("\nArray 5 (single zero): "); printArray(arr5, n5); printf("Zeros (linear): %d\n", countZerosLinear(arr5, n5)); printf("Zeros (binary): %d\n", countZerosBinary(arr5, n5)); printf("Zeros (recursive): %d\n", countZerosWrapper(arr5, n5)); break; case 2: { int n; if (readInteger("Enter array size (0-100): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 0 || n > 100) { printf("Size must be 0-100.\n"); break; } int *customArr = malloc(n * sizeof(int)); if (customArr == NULL && n > 0) { fprintf(stderr, "Memory allocation failed.\n"); break; } printf("Enter %d elements (only 0s and 1s, sorted):\n", n); for (int i = 0; i < n; i++) { int value; char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &value) != 0) { fprintf(stderr, "Invalid element.\n"); free(customArr); break; } if (value != 0 && value != 1) { printf("Only 0 and 1 allowed. Please try again.\n"); i--; continue; } /* Check sorted order */ if (i > 0 && value < customArr[i - 1]) { printf("Array must be sorted (all 0s before all 1s).\n"); i--; continue; } customArr[i] = value; } printf("\nCustom array: "); printArray(customArr, n); printf("Zeros (linear): %d\n", countZerosLinear(customArr, n)); printf("Zeros (binary): %d\n", countZerosBinary(customArr, n)); printf("Zeros (recursive): %d\n", countZerosWrapper(customArr, n)); free(customArr); break; } case 3: { printf("\n=== Performance Comparison ===\n"); /* Create a large array with half zeros, half ones */ int largeSize = 10000000; int *largeArr = malloc(largeSize * sizeof(int)); if (largeArr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } /* Fill: first half zeros, second half ones */ for (int i = 0; i < largeSize / 2; i++) { largeArr[i] = 0; } for (int i = largeSize / 2; i < largeSize; i++) { largeArr[i] = 1; } clock_t start, end; /* Linear scan */ start = clock(); int linearResult = countZerosLinear(largeArr, largeSize); end = clock(); demonstrateApproach("Linear scan", linearResult, start, end); /* Binary search */ start = clock(); int binaryResult = countZerosBinary(largeArr, largeSize); end = clock(); demonstrateApproach("Binary search", binaryResult, start, end); /* Recursive binary search */ start = clock(); int recursiveResult = countZerosWrapper(largeArr, largeSize); end = clock(); demonstrateApproach("Recursive binary search", recursiveResult, start, end); free(largeArr); break; } case 4: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Linear scan: O(n) */ int countZerosLinear(const int arr[], int n) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] == 0) { count++; } else { break; /* Since sorted, no more zeros after first 1 */ } } return count; } /* Iterative binary search: O(log n) */ int countZerosBinary(const int arr[], int n) { int left = 0; int right = n - 1; int firstOneIndex = n; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == 1) { firstOneIndex = mid; right = mid - 1; } else { left = mid + 1; } } return firstOneIndex; } /* Recursive binary search helper */ int countZerosRecursive(const int arr[], int left, int right) { if (left > right) { return left; /* Base case: first 1 index */ } int mid = left + (right - left) / 2; if (arr[mid] == 1) { return countZerosRecursive(arr, left, mid - 1); } else { return countZerosRecursive(arr, mid + 1, right); } } /* Wrapper for recursive binary search */ int countZerosWrapper(const int arr[], int n) { if (n == 0) return 0; return countZerosRecursive(arr, 0, n - 1); } /* Displays approach name, result, and time */ void demonstrateApproach(const char *name, int result, clock_t start, clock_t end) { double timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("%-25s: Result = %d, Time = %.3f ms\n", name, result, timeTaken); } /* Prints an array */ void printArray(const int arr[], int n) { if (n == 0) { printf("[]"); return; } printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]"); } /* 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 Approaches

1. countZerosLinear: O(n) linear scan, stops at first 1.
2. countZerosBinary: O(log n) iterative binary search to find first 1.
3. countZerosRecursive: O(log n) recursive binary search.
4. countZerosWrapper: Handles empty array for recursive approach.
5. Performance comparison: Demonstrates time difference on large arrays.

Expected Output (sample run)

text

=== Zero Counter for Sorted Binary Arrays === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Exit Enter choice: 1 === Sample Arrays === Array 1: [0, 0, 0, 1, 1, 1] Zeros (linear): 3 Zeros (binary): 3 Zeros (recursive): 3 Array 2 (all zeros): [0, 0, 0, 0, 0] Zeros (linear): 5 Zeros (binary): 5 Zeros (recursive): 5 Array 3 (all ones): [1, 1, 1, 1] Zeros (linear): 0 Zeros (binary): 0 Zeros (recursive): 0 Array 4 (empty): [] Zeros (linear): 0 Zeros (binary): 0 Zeros (recursive): 0 Array 5 (single zero): [0] Zeros (linear): 1 Zeros (binary): 1 Zeros (recursive): 1 --- Menu --- ... Enter choice: 3 === Performance Comparison === Linear scan : Result = 5000000, Time = 8.420 ms Binary search : Result = 5000000, Time = 0.001 ms Recursive binary search : Result = 5000000, Time = 0.002 ms

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Array

Accessing arr[0] or arr[n-1] on an empty array is undefined behavior.

c

int countZeros(const int arr[], int n) { if (arr[0] == 1) return 0; // BUG: empty array if (arr[n - 1] == 0) return n; // BUG: empty array }

Solution: Check n == 0 first: if (n == 0) return 0;

2. Integer Overflow in Mid Calculation

(left + right) / 2 can overflow for large values.

c

int mid = (left + right) / 2; // Potential overflow

Solution: Use left + (right - left) / 2.

3. Off-by-One in Binary Search

Incorrect loop bounds can skip elements or cause infinite loops.

c

while (left < right) { // May miss the correct element // ... }

Solution: Use while (left <= right) for inclusive bounds.

4. Unsorted Input

The binary search assumes sorted input. Unsorted arrays will give incorrect results.

c

int arr[] = {1, 0, 1, 0}; // Not sorted countZerosBinary(arr, 4); // Incorrect result

Solution: Validate sorted order or sort first.

5. Non-Binary Values

Input containing values other than 0 and 1 breaks the algorithm’s assumptions.

c

int arr[] = {0, 0, 2, 3, 1}; // Invalid binary array

Solution: Validate elements are 0 or 1.

6. Recursive Depth

Recursive binary search depth is O(log n), which is safe for typical array sizes. No stack overflow risk for n up to millions.

7. clock() Precision

clock() measures CPU time and may not be precise for very fast operations.

Solution: Use larger arrays or repeat operations for measurable differences.

8. Memory Allocation Failure

Large arrays may fail to allocate memory.

c

int *arr = malloc(10000000 * sizeof(int)); if (arr == NULL) { // Always check fprintf(stderr, "Memory allocation failed\n"); }

Solution: Always check malloc return value.

9. Array Size Type

Using int for array size can overflow for very large arrays.

c

int n = 10000000000; // Overflow

Solution: Use size_t for array sizes.

10. Cache Performance

Linear scan has better cache locality for small arrays; binary search jumps around memory. For very small arrays, linear scan may be faster.

Solution: Use linear scan for small arrays (n < 100), binary search for large arrays.

Summary & Best Practices

Counting zeros in a sorted binary array is a classic problem that demonstrates the power of binary search. While linear scan is O(n), binary search achieves O(log n) by exploiting the sorted property.

Key Takeaways

• Sorted binary array: all 0s followed by all 1s.
• Linear scan: O(n), simple but slow for large arrays.
• Binary search: O(log n), efficient for large arrays.
• Count of zeros = index of first 1 = last zero index + 1.
• Handle edge cases: empty array, all zeros, all ones.
• Use left + (right - left) / 2 to avoid overflow.

Best Practices

1. Use binary search for large arrays (n > 1000).
2. Use linear scan for small arrays (n < 100) for simplicity.
3. Check for empty array before accessing elements.
4. Handle all-zeros and all-ones cases explicitly for optimization.
5. Use size_t for array sizes instead of int.
6. Avoid integer overflow in mid calculation.
7. Validate input to ensure array is sorted and binary.
8. Document the algorithm’s complexity in comments.
9. Test with edge cases: empty, single element, all zeros, all ones.
10. Prefer iterative over recursive for large arrays to avoid stack overhead.

By mastering this algorithm, you’ll understand binary search fundamentals and be prepared for variations like finding first/last occurrences, counting specific elements, and searching in rotated arrays.