given a sorted array of numbers, how do i find the size of numbers less than x

Question

Possible Duplicate:
finding all numbers less than x in a BST

How would I modify a binary search to find the number of numbers in a sorted array that are less than a certain number?

Answer 1

If you have an already sorted array of numbers simply find the insertion point for your item in the sorted array usng a binary search algorithm. The index of the insertion point gives you the number of elements that are less than your target number.

In your comments you raised two good questions:

• What if the number is not in the list?

To handle this you keep searching until you find the point where the number should be if it were present, that is the index where the current element is greater than x and the previous element is less than x.

• What if there are duplicates?

To handle this, instead of stopping when you first find an element, continue searching until you lower bound and upper bound meet. If you hit a value that is equal to x treat it in the same way as if you found a number that was too high and continue bisecting.

Answer 2

Binary search for the largest number lower than your given number. Once you have its position, that position also directly relates to the count you're interested in.

This pseudocode should get you on the right track, but I haven't tested it. k = given number

while left < right
    mid = (left + right) / 2
    if arr[mid] >= k // too big, not interested
        right = mid;
    else             // maybe too small, try bigger values
        left = mid + 1

 right - 1 or left - 1 (they're equal) is the position you're after.

For example: 8 11 13 20 50, k = 19

left = 1, right = 5
mid = 3
arr[3] = 13 < 19 => left = 4

left = 4, right = 5
mid = 4
arr[4] = 20 >= 19 => right = 4

left >= right => left - 1 = 4 - 1 = 3 is the position you're after

Answer 3

Return all numbers less than the index of the value returned by the binary search.

Answer 4

Find number and check index.

Answer 5

Since this is specifically an array of numbers and not just comparable objects, you might want to look at interpolation search. If the numbers are uniformly distributed, it can find the index in O(log log n) time instead of O(log n).