Understanding the Smaller or Equal Elements Problem | Binary Search Problem | Interview Bit

In technical interviews, Binary Search problems are a common theme, often tested to evaluate a candidate’s understanding of efficient search algorithms. One such problem is the Smaller or Equal Elements problem, which is frequently encountered in coding interviews and competitive programming challenges. This problem involves finding the number of elements in a sorted array that are smaller than or equal to a given target value.

To tackle this problem, an efficient approach using Binary Search is preferred over a simple linear search due to its logarithmic time complexity, making it ideal for large datasets.

Problem Statement

Given a sorted array A of n integers and a target value X, the objective is to find the number of elements in the array that are less than or equal to X.

Example Scenario

Consider the following example:

Input:

A = [1, 3, 5, 7, 9]
X = 6

Output:

The number of elements less than or equal to 6 is 3 (elements: 1, 3, 5).

In this case, the elements 1, 3, and 5 are all less than or equal to 6.

Also Read: 590. N-ary Tree Post order Traversal | n Array Tree Post Order Traversal LeetCode Solution in Java

---

Approach: Leveraging Binary Search

The naive approach to solving this problem would be to iterate through the entire array, count the number of elements that satisfy the condition, and then return the count. However, this approach runs in O(n) time, which is inefficient for large arrays.

To optimize the solution, we can utilize Binary Search to find the upper bound of the target X. The upper bound here refers to the index of the smallest element that is greater than X. The number of elements less than or equal to X will then be the index of this element.

Binary Search Algorithm for the Problem

1. Initialization: Start with two pointers, low at the beginning of the array (0) and high at the end of the array (n-1).
2. Mid Calculation: Calculate the middle index mid = low + (high - low) / 2.
3. Comparison:
   • If A[mid] <= X, move the low pointer to mid + 1 since all elements up to mid are smaller than or equal to X.
   • If A[mid] > X, move the high pointer to mid - 1.
4. Termination: When low exceeds high, the low pointer will be at the index of the first element greater than X. The count of elements less than or equal to X is given by low.
5. Return the Count: The result is the low index.

Also Read: Two Sum II – Input Array Is Sorted | Two Sum II – Input Array Is Sorted LeetCode Solution in Java

---

Java Implementation

Below is the Java code that implements the Binary Search approach to solve the Smaller or Equal Elements problem:

public class SmallerOrEqualElements {

    public static int countSmallerOrEqual(int[] A, int X) {
        int low = 0;
        int high = A.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (A[mid] <= X) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;
    }

    public static void main(String[] args) {
        int[] A = {1, 3, 5, 7, 9};
        int X = 6;

        int result = countSmallerOrEqual(A, X);
        System.out.println("The number of elements less than or equal to " + X + " is: " + result);
    }
}

Explanation

• low: Tracks the lower bound of the current search space.
• high: Tracks the upper bound of the current search space.
• mid: The middle index, calculated to avoid overflow.
• low pointer post-loop: Represents the count of elements less than or equal to X.

Also Read: Solving Arithmetic Progression Problem | Step-by-Step Guide and Examples

---

Dry Run: Understanding Step by Step

Let’s walk through the dry run of the Binary Search algorithm with the provided input:

Input

A = [1, 3, 5, 7, 9]
X = 6

Initial State

low = 0, high = 4

Iteration 1

• Calculate mid = 0 + (4 - 0) / 2 = 2.
• A[mid] = 5, which is less than 6.
• Move low to mid + 1 = 3.

Iteration 2

• Calculate mid = 3 + (4 - 3) / 2 = 3.
• A[mid] = 7, which is greater than 6.
• Move high to mid - 1 = 2.

Termination

• Now, low = 3, high = 2.
• Since low > high, exit the loop.

Result

• The low pointer is at index 3, indicating there are 3 elements less than or equal to 6 (i.e., 1, 3, 5).

Also Read: Copy Array | Copying Array and its Elements | Java Programming | Code with Kamlesh

---

Why Binary Search?

Binary Search is a powerful tool when dealing with sorted arrays. The key advantage here is its logarithmic time complexity, O(log n), which is significantly faster than linear search, especially when dealing with large data sets.

---

Common Variations of the Problem

1. Finding the First Occurrence of an Element: Similar to our approach, but stop as soon as the element is found.
2. Finding the Last Occurrence of an Element: Adjust the binary search to find the last occurrence by shifting the bounds accordingly.
3. Counting Elements Greater than X: A variation where instead of smaller or equal, we find elements greater than a given value X.

Conclusion

The Smaller or Equal Elements problem is an excellent example of how Binary Search can be applied to solve problems efficiently, especially when dealing with large datasets. Understanding this approach not only helps in cracking coding interviews but also enhances your algorithmic thinking. By mastering Binary Search, you can solve a wide range of problems that involve searching and counting in sorted arrays.

Also Read: Count Inversions in an Array | Coding Interview Question | Count Inversions Merge Sort

---

Frequently Asked Questions

What if the array is not sorted?
The Binary Search algorithm requires a sorted array to function correctly. If the array is not sorted, you must sort it before applying the Binary Search, which would add an O(n log n) time complexity.

How does the Binary Search ensure efficiency in this problem?
Binary Search divides the search space in half with each iteration, ensuring that the number of operations is logarithmic relative to the input size, making it highly efficient for large arrays.

Can Binary Search be used to find the exact number of occurrences of X?
Yes, by finding the first and last occurrences of X using modified binary searches, you can calculate the exact number of times X appears in the array.

How to handle edge cases like an empty array or an array with all elements greater or smaller than X?
For an empty array, the function should return 0 immediately. For arrays where all elements are smaller than X, the function will return the size of the array. Conversely, if all elements are greater, it will return 0.

What is the difference between Binary Search and Linear Search in this context?
Linear Search checks each element sequentially, making it O(n), whereas Binary Search uses a divide-and-conquer strategy to reduce the search space logarithmically, making it O(log n).

Is Binary Search applicable to all types of arrays?
Binary Search is only applicable to sorted arrays. If the array is unsorted, Binary Search cannot guarantee finding the correct position or element.

Pro Tip: Always think of Binary Search as an option when you encounter problems involving sorted data and search operations. It could be the key to unlocking a more efficient solution!