Binary Searchable Count

Intuition

An element is counted if a normal binary search on the given array can actually encounter that value. The array is not necessarily sorted, so being present is not enough: the search path may move left or right based on misleading comparisons and skip the target. The implementation directly simulates that search for each value and counts the values that are found.

Algorithm

1Initialize count = 0.
2For every value arr[i], run a standard binary search over the whole array with target = arr[i].
3During the search, compute mid = l + (r-l)/2.
4If arr[mid] equals target, the value is binary searchable, so increment count.
5If arr[mid] is less than target, move l to mid + 1; otherwise move r to mid - 1.
6After all values are tested, return count.
7Time Complexity: O(n log n), because n values each run one binary search.
8Space Complexity: O(1), because only pointers and counters are used.

Example Walkthrough

Input: arr = [2, 1, 3]

1.Target 2: mid is index 1 with value 1. Since 1 < 2, search moves right to index 2 with value 3, then moves left and fails. So 2 is not counted.
2.Target 1: the first mid is index 1 with value 1, so 1 is counted.
3.Target 3: mid value 1 sends the search right, then index 2 has value 3, so 3 is counted.
4.Two values are searchable by the binary-search path.

Output: 2

Common Pitfalls

•Do not assume every present value is searchable; binary search can fail on an unsorted array.
•Use l + (r-l)/2 for the midpoint to avoid overflow in general binary-search code.
•This implementation counts each original array value independently, even if equal values appear more than once.

Binary Searchable Count.java

Java

// Approach: For every array value, simulate ordinary binary search over the current array
// and count it if that search can encounter the target. This directly tests whether each
// value is searchable by the binary-search decision path.
// Time: O(n log n) Space: O(1)

class Solution {

    public int binarySearchable(int[] arr) {
        int n = arr.length;
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (canBeFound(arr, arr[i])) {
                count++;
            }
        }

        return count;
    }

    private boolean canBeFound(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return false;
    }
};

Was this solution helpful?