Binary search returning wrong answer many times

Question

I've implemented the iterative binary search algorithm which returns the index of the found element (-1 if the element isn't in the array):

public static int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

When I try to test it on an element that is not in the array it returns the correct answer, when I tried it with the array: {1,5,23,111} and the target is the number 5 it returned the correct result which is 1 in this case, however when I tried with that same array but the number 111 it returned -1, I've also tried with different arrays and multiple target numbers and many times it returned -1 even though the number is present in the array, any help on why this is happening?

What happens when you run this in a debugger? – ControlAltDel Oct 23 '19 at 17:37 — ControlAltDel, Oct 23 '19 at 17:37

score 2 · Accepted Answer · answered Oct 23 '19 at 17:44

Your left/right advancement is backwards. When the element at the current mid position is less than the target, then you need to search the right half, and when the element at the current mid position is greater than the target (else block), you need to search the left half.

The only reason you found 5 correctly is that mid happened to be correct in the first iteration.

Switch your statements in the else if and else blocks.

else if (array[mid] < target) { left = mid + 1; }
else { right = mid - 1; }

Or alternatively reverse the sense of comparison for the else if condition.

else if (array[mid] > target) { right = mid - 1; }
else { left = mid + 1; }

Arvind Kumar Avinash · Answer 2 · 2019-10-23T18:33:18.560

There is some logical problem in your program.

The first problem is using else with the if condition containing a return statement. Since the method will return when the if condition is true, putting an else is useless. The use of else is required to choose either of the two options (i.e. not both of them). After using the return statement with the first option, you are already disallowing the second option.
The second problem is misplacing the calculation for right and left variables. The logic should be: Ignore the left half if the target is greater than the number at mid, and to do this, simply advance left by one position beyond mid; otherwise (i.e. if the target is less than the number at mid), ignore the right half by moving right backwards by one position.

Given below is the working program:

public class BinarySearchDemo {

    public static void main(String[] args) {
        int arr[] = { 1, 5, 23, 111 };
        System.out.println(binarySearch(arr, 23));
        System.out.println(binarySearch(arr, 20));
    }

    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - 1) / 2;
            if (array[mid] == target) {
                return mid;
            }
            if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

Output:

2
-1

Instead of just fixing the issue, you should explain it so the op can learn — RobOhRob, Oct 23 '19 at 17:52

score 1 · Answer 3 · answered Oct 23 '19 at 17:46

The problem is when you are updating left and right. You are updating them in the incorrect if statements.

When array[mid] < target, you want to update the left pointer and search in the right subarray, and vice versa.

So your updates should look like this:

else if (array[mid] < target) { left = mid + 1; } 
else { right = mid - 1; }

score 1 · Answer 4 · answered Oct 23 '19 at 17:58

Wanted to add as comment, but cannot comment yet

After you've fixed your code with correct logic (as in answers above), here is something to improve to your code:
Don't do this: int mid=(left+right)/2;
Do this: int mid = low + ((high - low) / 2); or this int mid = (low + high) >>> 1;

Refer this post.

Binary search returning wrong answer many times

4 Answers4