Baseline Binary Search · 1D Arrays O(log N) · O(1)
A device trace stores alarm codes in non-decreasing order, and reliability engineers need to know how many times one code fired. Because equal codes sit next to each other, the count is simply the width of that block. Measure the block without scanning the whole trace.
Input: An integer N, an array Arr of N integers sorted in non-decreasing order, and an integer X.
Output: The number of times X appears in Arr.
1 <= N <= 10^51 <= Arr[i] <= 10^91 <= X <= 10^9Arr is sorted in non-decreasing orderInput: {"N":7,"Arr":[1,1,2,2,2,2,3],"X":2}
Output: 4
Code 2 forms a block of four consecutive entries.
Input: {"N":7,"Arr":[1,1,2,2,2,2,3],"X":4}
Output: 0
Code 4 never fired, so the block width is zero.