Why is there still an error case in this binary search of sorted array scenario?

Question

For the record, I came across this question on some web coding site, but I am really interested in what I missed rather than scores. Here it goes:

Implement function countNumbers that accepts a sorted array of unique integers and counts the number of array elements that are less than the parameter lessThan.

For example, SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4) should return 2 because there are two array elements less than 4.

I give the following solution, however, I just can not figure out in what scenario will it fail? (the site says it fails 1 out of 4 tests). And I also am not sure what kind of assumption I can have for value lessThan.

public class SortedSearch {
    public static int countNumbers(int[] sortedArray, int lessThan) {

        if (sortedArray == null || sortedArray.length == 0)
            return 0;

        if (sortedArray.length == 1) {
            return sortedArray[0] < lessThan? 1:0;
        }

        int left = 0;
        int right = sortedArray.length-1;
        int middle = 0;

        while(left<right) {
            middle = left + (right-left)/2;
            if (sortedArray[middle]<lessThan) {
                left = middle+1;
            } else if (sortedArray[middle]>lessThan) {
                right = middle-1;
            } else {
                return middle;
            }        
        }
        return left;

    }

    public static void main(String[] args) {
        System.out.println(SortedSearch.countNumbers(new int[] { 1, 3, 5 }, 4));
    }
}

Try `System.out.println(SortedSearch.countNumbers(new int[] { 1, 3 }, 4));` — M A, Aug 18 '18 at 10:50
The fun in such challenges is to write your own tests. This is perfect to do some work with junit. Simply think about relevant cases, such: odd number of entries, even number, corner cases where the result should be 0 or 1. Just saying: if this about learning, then use it as opportunity to learn testing. — GhostCat, Aug 18 '18 at 10:51
Also is there a better way to write it (in terms of index or else) so that i can write fewer 'if's on corner cases? — user1559625, Aug 18 '18 at 11:03
@user1559625 We have answered to your question. Can you please considering commenting whether the answer helped you or not, and accept the answer that answers your question the best? — nice_dev, Aug 20 '18 at 04:49
@vivek_23 sure, i just marked the helpful answer, but has not accepted one 'cause i still have some doubt on the correctness. — user1559625, Aug 20 '18 at 05:37
@user1559625 ok, fair enough. I recommended a small change to your code. Did it work or did it not work? — nice_dev, Aug 20 '18 at 06:26

score 2 · Answer 1 · answered Aug 18 '18 at 11:04

Your code is currently doing classic binary search. You need to modify that to include your cases.

For ex. try your code with below test cases:

{ 1, 3, 5 }, 4) -> should output 2
{ 1, 3, 5 }, 2) -> should output 1
{ 1, 3, 5 }, 3) -> should output 1
{ 1, 3, 5 }, 6) -> should output 3
{ 1, 3, 5 }, 0) -> should output 0

most of these are failing with existing code.

Our goal is to find out the point where middle is less than given number and middle + 1 is greater than it. Of course we can do this using binary search (modified).

I modified your code for classic binary search to include these cases (and comments added in the code):

while (left <= right) {
    middle = left + (right - left) / 2;
    if (sortedArray[middle] < lessThan && (middle + 1) < sortedArray.length
            && sortedArray[middle + 1] > lessThan) {
        // we have the point where middle is less and middle+1 is greater than given num
        return middle + 1;
    } else if (sortedArray[middle] == lessThan) {
        // we have found the number itself
        return middle;
    } else if (sortedArray[middle] < lessThan) {
        // recur in right part
        left = middle + 1;
    } else if (sortedArray[middle] > lessThan) {
        // recur in left part
        right = middle - 1;
    }
}

// given number is either lesser/bigger than all elements in the array
return lessThan < sortedArray[0] ? 0 : sortedArray.length;

how is last line handle 'bigger than all elements in the array' if it compares only lessThan with sortedArray[0]? — user1559625, Aug 18 '18 at 11:27
@user1559625 if the code execution goes till the last line, then its clear that would could not find any `middle` point we wanted. So there are only two cases left, given number is less that all elements or given number is greater than all elements. — Shanu Gupta, Aug 18 '18 at 11:38
thanks, and also why do we need '&& (middle + 1) < sortedArray.length' in the code? — user1559625, Aug 18 '18 at 11:53
@user1559625 to avoid array out of bound exception in condition -> `sortedArray[middle + 1] > lessThan` — Shanu Gupta, Aug 18 '18 at 11:55
with {1, 3, 5, 7} 4, initially left=0, right=3, finally left=right=middle=2, and we do not have '// we have the point where middle is less and middle+1 is greater than given num'. in other words, using binary search we can not guarantee that at the end middletarget — user1559625, Aug 20 '18 at 03:09

score 1 · Accepted Answer · answered Aug 18 '18 at 14:32

1

Make only 1 change.

while(left < right)

to

while(left <= right)

answered Aug 18 '18 at 14:32

nice_dev

17,053
2
21
35

Matt Timmermans · Answer 3 · 2018-08-19T01:14:40.200

Binary searches like yours are one of my pet peeves. I wrote about what I think is the best way to usually write one over here: How can I simplify this working Binary Search code in C?

This is particularly well suited to your case. Since you are trying to find a position instead of an element, you can simplify your code and make it faster by having only one comparison per iteration like this:

public static int countNumbers(int[] sortedArray, int lessThan) {
    int start = 0, limit = sortedArray.length;
    while(start < limit) {
        int test = start + ((limit-start)>>1);
        if (sortedArray[test] < lessThan) {
            start = test+1;
        } else {
            limit = test;
        }
    }
    return start;
}

Note that there are no special cases to take care of, and this will also work if the array contains repeated elements.

Why is there still an error case in this binary search of sorted array scenario?

3 Answers3