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?

Answer 1

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; }