Tag binary search

Count Smaller Than X in an Array: A Comprehensive Tutorial

Counting elements smaller than a given value X in an array is a fundamental operation in data analysis and algorithm design. This problem tests understanding of array traversal, comparison operations, and optimization techniques. It serves as a building block for more complex algorithms like rank finding, percentile calculation, and data filtering.

This tutorial provides an in-depth exploration of counting elements smaller than X in C: multiple approaches, handling sorted and unsorted arrays, performance optimization, edge cases, and best practices.

---

Conceptual Introduction & Fundamentals

What Does “Count Smaller Than X” Mean?

Given an array of integers and a target value X, count how many elements in the array are strictly less than X.

Example:

text

Array: [10, 5, 20, 15, 25, 30] X = 20 Elements smaller than 20: 10, 5, 15 Count = 3

Problem Variations

1. Strictly less than: Elements < X
2. Less than or equal to: Elements <= X
3. Greater than: Elements > X
4. Within range: Elements between [lower, upper]

Why This Problem Matters

• Data filtering: Find items below a threshold (price, score, temperature).
• Rank calculation: Determine position of an element in sorted order.
• Percentile computation: Find what percentage of data falls below a value.
• Algorithm foundation: Building block for selection algorithms and order statistics.
• Database queries: COUNT WHERE value < X.

Approaches Overview

Approach	Time Complexity	Space Complexity	Requirement
Linear scan	O(n)	O(1)	None (works on unsorted)
Binary search (sorted)	O(log n)	O(1)	Sorted array
Sorting + binary search	O(n log n)	O(1) or O(n)	Sorting cost
Frequency count	O(n + range)	O(range)	Small value range

---

Syntax & Core Mechanics

Approach 1: Linear Scan (Unsorted Array)

Traverse the array and count elements less than X.

c

#include <stdio.h> int countSmallerThanX(const int arr[], int n, int x) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] < x) { count++; } } return count; } int main(void) { int arr[] = {10, 5, 20, 15, 25, 30}; int n = sizeof(arr) / sizeof(arr[0]); int x = 20; int count = countSmallerThanX(arr, n, x); printf("Elements smaller than %d: %d\n", x, count); return 0; }

Expected output:

text

Elements smaller than 20: 3

Time complexity: O(n)

Approach 2: Binary Search (Sorted Array)

If the array is sorted, use binary search to find the first element >= X. The count of smaller elements equals that index.

c

#include <stdio.h> int countSmallerSorted(const int arr[], int n, int x) { int left = 0; int right = n - 1; int result = n; /* Default: all elements are smaller */ while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] >= x) { result = mid; /* Record position */ right = mid - 1; /* Search left */ } else { left = mid + 1; /* Search right */ } } return result; /* Number of elements < X */ } int main(void) { int arr[] = {5, 10, 15, 20, 25, 30}; int n = sizeof(arr) / sizeof(arr[0]); int x = 20; int count = countSmallerSorted(arr, n, x); printf("Elements smaller than %d: %d\n", x, count); return 0; }

Expected output:

text

Elements smaller than 20: 3

Time complexity: O(log n)

Approach 3: Count Less Than or Equal To

Variation that counts elements <= X.

c

#include <stdio.h> int countLessEqual(const int arr[], int n, int x) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] <= x) { count++; } } return count; } int main(void) { int arr[] = {10, 20, 30, 40, 50}; int n = sizeof(arr) / sizeof(arr[0]); int x = 30; int count = countLessEqual(arr, n, x); printf("Elements <= %d: %d\n", x, count); return 0; }

Expected output:

text

Elements <= 30: 3

Approach 4: Count Within Range

Count elements in range [lower, upper].

c

#include <stdio.h> int countInRange(const int arr[], int n, int lower, int upper) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] >= lower && arr[i] <= upper) { count++; } } return count; } int main(void) { int arr[] = {10, 20, 30, 40, 50, 60}; int n = sizeof(arr) / sizeof(arr[0]); int lower = 20, upper = 50; int count = countInRange(arr, n, lower, upper); printf("Elements in [%d, %d]: %d\n", lower, upper, count); return 0; }

Expected output:

text

Elements in [20, 50]: 4

Approach 5: Count Smaller for Each Element

For each element, count how many elements are smaller than it.

c

#include <stdio.h> #include <stdlib.h> int *countSmallerForEach(const int arr[], int n) { int *result = malloc(n * sizeof(int)); if (result == NULL) return NULL; for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < n; j++) { if (arr[j] < arr[i]) { count++; } } result[i] = count; } return result; } int main(void) { int arr[] = {10, 20, 30, 40}; int n = sizeof(arr) / sizeof(arr[0]); int *counts = countSmallerForEach(arr, n); if (counts != NULL) { for (int i = 0; i < n; i++) { printf("Elements smaller than %d: %d\n", arr[i], counts[i]); } free(counts); } return 0; }

Expected output:

text

Elements smaller than 10: 0 Elements smaller than 20: 1 Elements smaller than 30: 2 Elements smaller than 40: 3

---

Full Practical Code Example with Explanation

This program demonstrates counting elements smaller than X in a realistic scenario: a student score analyzer that counts students below a passing threshold.

Program: Student Score Analyzer

c

/** * count_smaller_than_x.c * Counts elements smaller than X in arrays. * Demonstrates linear scan, binary search, and range counting. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_STUDENTS 100 /* Function prototypes */ int countSmallerLinear(const int arr[], int n, int x); int countSmallerSorted(const int arr[], int n, int x); int countLessEqual(const int arr[], int n, int x); int countInRange(const int arr[], int n, int lower, int upper); void sortArray(int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demonstrateApproach(const char *name, int result, clock_t start, clock_t end); int main(void) { int choice; char buffer[MAX_LINE_LEN]; /* Test arrays */ int unsortedScores[] = {85, 45, 92, 60, 78, 35, 70, 55}; int nUnsorted = sizeof(unsortedScores) / sizeof(unsortedScores[0]); int sortedScores[] = {35, 45, 55, 60, 70, 78, 85, 92}; int nSorted = sizeof(sortedScores) / sizeof(sortedScores[0]); printf("=== Student Score Analyzer ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Count Scores Below Passing (Linear)\n"); printf("2. Count Scores Below Passing (Binary Search)\n"); printf("3. Count Scores in Grade Range\n"); printf("4. Count <= Threshold\n"); printf("5. Performance Comparison\n"); printf("6. 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: { int passingScore; if (readInteger("Enter passing score: ", &passingScore) != 0) { fprintf(stderr, "Invalid score.\n"); break; } printf("\nUnsorted scores: "); printArray(unsortedScores, nUnsorted); int count = countSmallerLinear(unsortedScores, nUnsorted, passingScore); printf("Students below %d: %d\n", passingScore, count); break; } case 2: { int passingScore; if (readInteger("Enter passing score: ", &passingScore) != 0) { fprintf(stderr, "Invalid score.\n"); break; } printf("\nSorted scores: "); printArray(sortedScores, nSorted); int count = countSmallerSorted(sortedScores, nSorted, passingScore); printf("Students below %d: %d\n", passingScore, count); break; } case 3: { int lower, upper; if (readInteger("Enter lower bound: ", &lower) != 0 || readInteger("Enter upper bound: ", &upper) != 0) { fprintf(stderr, "Invalid bounds.\n"); break; } printf("\nScores: "); printArray(unsortedScores, nUnsorted); int count = countInRange(unsortedScores, nUnsorted, lower, upper); printf("Students in [%d, %d]: %d\n", lower, upper, count); break; } case 4: { int threshold; if (readInteger("Enter threshold: ", &threshold) != 0) { fprintf(stderr, "Invalid threshold.\n"); break; } printf("\nScores: "); printArray(unsortedScores, nUnsorted); int count = countLessEqual(unsortedScores, nUnsorted, threshold); printf("Students <= %d: %d\n", threshold, count); break; } case 5: { printf("\n=== Performance Comparison ===\n"); int largeSize = 10000000; int *largeArr = malloc(largeSize * sizeof(int)); if (largeArr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } /* Fill with random values */ srand(42); for (int i = 0; i < largeSize; i++) { largeArr[i] = rand() % 1000; } int x = 500; clock_t start, end; /* Linear scan on unsorted */ start = clock(); int linearResult = countSmallerLinear(largeArr, largeSize, x); end = clock(); demonstrateApproach("Linear scan", linearResult, start, end); /* Sort for binary search */ start = clock(); sortArray(largeArr, largeSize); end = clock(); printf("Sorting time: %.3f ms\n", ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0); /* Binary search on sorted */ start = clock(); int binaryResult = countSmallerSorted(largeArr, largeSize, x); end = clock(); demonstrateApproach("Binary search", binaryResult, start, end); free(largeArr); break; } case 6: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Linear scan: O(n), works on unsorted arrays */ int countSmallerLinear(const int arr[], int n, int x) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] < x) { count++; } } return count; } /* Binary search: O(log n), requires sorted array */ int countSmallerSorted(const int arr[], int n, int x) { int left = 0; int right = n - 1; int result = n; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] >= x) { result = mid; right = mid - 1; } else { left = mid + 1; } } return result; } /* Count elements <= x: O(n) */ int countLessEqual(const int arr[], int n, int x) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] <= x) { count++; } } return count; } /* Count elements in range [lower, upper]: O(n) */ int countInRange(const int arr[], int n, int lower, int upper) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] >= lower && arr[i] <= upper) { count++; } } return count; } /* Sorts array using bubble sort (simple, O(n^2)) */ void sortArray(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } /* Displays approach 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("%-20s: Count = %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. countSmallerLinear: O(n) linear scan for unsorted arrays.
2. countSmallerSorted: O(log n) binary search for sorted arrays.
3. countLessEqual: Counts elements <= X.
4. countInRange: Counts elements within [lower, upper].
5. sortArray: Sorts array (bubble sort for simplicity).
6. Performance comparison: Shows trade-off between linear scan and sorting + binary search.

Expected Output (sample run)

text

=== Student Score Analyzer === --- Menu --- 1. Count Scores Below Passing (Linear) 2. Count Scores Below Passing (Binary Search) 3. Count Scores in Grade Range 4. Count <= Threshold 5. Performance Comparison 6. Exit Enter choice: 1 Enter passing score: 60 Unsorted scores: [85, 45, 92, 60, 78, 35, 70, 55] Students below 60: 3 --- Menu --- ... Enter choice: 2 Enter passing score: 60 Sorted scores: [35, 45, 55, 60, 70, 78, 85, 92] Students below 60: 3 --- Menu --- ... Enter choice: 3 Enter lower bound: 50 Enter upper bound: 80 Scores: [85, 45, 92, 60, 78, 35, 70, 55] Students in [50, 80]: 4 --- Menu --- ... Enter choice: 4 Enter threshold: 70 Scores: [85, 45, 92, 60, 78, 35, 70, 55] Students <= 70: 5 --- Menu --- ... Enter choice: 5 === Performance Comparison === Linear scan : Count = 5000000, Time = 8.234 ms Sorting time: 0.000 ms Binary search : Count = 5000000, Time = 0.001 ms

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Strict vs. Non-Strict Comparison

Using < vs <= changes the result. Be clear about the requirement.

c

/* Strictly less than */ if (arr[i] < x) count++; /* Less than or equal to */ if (arr[i] <= x) count++;

Solution: Document which comparison is required.

2. Binary Search on Unsorted Array

Using binary search on an unsorted array gives incorrect results.

c

int arr[] = {50, 10, 40, 20, 30}; // Unsorted countSmallerSorted(arr, 5, 25); // Incorrect

Solution: Sort first or use linear scan.

3. Empty Array

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

c

int countSmallerSorted(const int arr[], int n, int x) { if (arr[n - 1] < x) return n; // BUG: n == 0 }

Solution: Check n == 0 first.

4. All Elements Smaller or Larger

Handle cases where all elements are < X or all are >= X.

c

/* All smaller: returns n */ /* All larger: returns 0 */

Solution: Initialize result appropriately in binary search.

5. Integer Overflow in Mid Calculation

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

c

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

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

6. Sorting Cost

Sorting for binary search costs O(n log n). For single queries on unsorted arrays, linear scan is better.

Solution: Use linear scan for single queries; sort only for multiple queries.

7. Duplicate Elements

Binary search for < X should return the first index where arr[index] >= X.

c

/* For duplicates: [1, 2, 2, 3], X = 2 */ /* Count smaller than 2 = 1 (only index 0) */

Solution: Use >= in binary search condition.

8. Negative Numbers

Comparisons work correctly with negative numbers, but ensure the array is sorted for binary search.

c

int arr[] = {-10, -5, 0, 5, 10}; countSmallerSorted(arr, 5, 0); // Returns 2 (-10, -5)

9. Large Arrays and Performance

Linear scan is O(n) per query. For many queries, sorting + binary search or frequency count may be better.

Solution: Consider preprocessing (sorting, prefix sums) for repeated queries.

10. Memory Considerations

• Linear scan: O(1) space.
• Binary search: O(1) space (iterative) or O(log n) (recursive).
• Sorting: O(1) to O(n) space depending on algorithm.
• Frequency count: O(range) space.

---

Summary & Best Practices

Counting elements smaller than X is a fundamental operation with applications in filtering, ranking, and data analysis. Linear scan works on unsorted arrays in O(n); binary search achieves O(log n) on sorted arrays.

Key Takeaways

• Linear scan: O(n), works on any array.
• Binary search: O(log n), requires sorted array.
• Count smaller than X = index of first element >= X in sorted array.
• Handle edge cases: empty array, all smaller, all larger, duplicates.
• Use < for strict, <= for inclusive comparison.

Best Practices

1. Use linear scan for single queries on unsorted arrays.
2. Sort + binary search for multiple queries on the same array.
3. Check for empty arrays before processing.
4. Use left + (right - left) / 2 to avoid overflow.
5. Document strict vs. non-strict comparison requirements.
6. Handle duplicates correctly in binary search.
7. Consider sorting cost when choosing approach.
8. Use size_t for array sizes.
9. Test with edge cases: empty, single element, all equal, all smaller/larger.
10. Profile performance for large arrays and many queries.

By mastering this operation, you’ll build a foundation for more complex algorithms like selection, ranking, and order statistics.