Binary search an integer array

Question

I'd like this code to be improved

package com.array.demo;

public class BinarySearchMethod {

public static void main(String[] args) {

    int[] arr = { 2, 4, 5, 6, 8, 9, 11, 15, 17, 19, 22, 111, 117, 234, 543 };

    int search = 2;
    BinarySearchMethod b = new BinarySearchMethod();
    int size = arr.length;

    int searchPos = b.binarySearch(arr, size, search);

    if (searchPos == -1) {
        System.out.println("Element not found");
    } else {
        System.out.println("Element found in the position " + searchPos);
    }

}

public int binarySearch(int[] arr, int size, int search) {
    int start = 0;
    int end = size - 1;

    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == search) {
            return mid;
        } else if (arr[mid] < search) {
            end = mid - 1;

        } else {
            start = mid + 1;
        }
    }

    return -1;

}

}

Answer 1

For beginner code, this is quite good. I am impressed. Good enough for me to assume you have worked from some example code. That is not a criticism, everyone does that (me too).

Still, many examples are based on other examples, and they have some issues that are 'historical' in nature, and then there are some practices in Java which make sense which are not visible in your code.

Style

Really, it's good, no big problems.

There is an extra empty-line in the middle of your if/else/else statement which is inconsistent. If I were to be extremely nit-picky, I would say that I personally would not put the empty line after the return statement (but like you I also would put one before the statement).

Order of comparison.... I am not sure why I dislike this one, and I have no reference for it, but, you have the line:

} else if (arr[mid] < search) {

and I would strongly prefer it to be:

} else if (search > arr[mid]) {

'Finally', the arr and search parameters to your method are constants, and are not changed. You should show this by adding 'final' to the declaration:

final int[] arr, ...., final int search

Mid Point Bug

There is a 'famous' bug in your code.

Basically, for large arrays, you risk overflowing the calculation. Your code should be:

int mid = start + (end - start) / 2;

Generalized search

In Java it is common practice to have a general method that will search in any sub-part of the array. Then, there should also be a version which searches the whole array.

Your method is unusual because it does neither..... it searches sub array sections, but only from the beginning (it has a size argument...). Your method should look like:

public int binarySearch(int[] arr, int start, int length, int search) {
    int end = start + length - 1;

In addition, you should have the 'simplified search everything method' that looks like:

public int binarySearch(int[] arr, int search) {
    return binarySearch(arr, 0, arr.length, search);
}

Input Validation

It is common in Java to validate the inputs. You should have this as your first lines:

if (start < 0 || start >= arr.length) {
    throw new IllegalArgumentException("Invalid start index " + start + " in array of size " + arr.length);
}

if (length < 0 || start + length > arr.length) {
    throw new IllegalArgumentException("Invalid length " + length + " in array of size " + arr.length + " and start from " + start);
}

Redundant else

You have the following code:

    if (arr[mid] == search) {
        return mid;
    } else if (arr[mid] < search) {
        end = mid - 1;

    } else {
        start = mid + 1;
    }

Because the first part has return mid;, there is no need for it to be an else afterwards:

    if (arr[mid] == search) {
        return mid;
    }

    if (arr[mid] < search) {
        end = mid - 1;

    } else {
        start = mid + 1;
    }

A return statement inside an if block means that the block will never complete normally. This is considered to be good practice in Java (both having 'early returns' and also removing the else when you have an early return).

Insertion Point

One of the features of Java's library functions for binary search (and what many people find complicated) is the "insertion point". This is a 'clever' way for the method to say: Well, I could not find the value when I searched, but, if it as here, it would need to go at position x.

So, in a small array [1, 3, 5], if we were to search for 2, it is not there, but, if it were to be inserted, it would be at position 1 (where the 3 is now). How has java 'standardised' for showing you this?

It returns a negative value for when the value is not found. It would be 'nice' if it could return just -1 if the value was not found but should be inserted at position +1. Unfortunately, if the value should be inserted at position 0, then it can't return -0, so, it has to take the negative of the insertion point, and then subtract 1. So, an insertion point of 0 becomes -1, an insertion point of 1 becomes -2, and so on.

This is actually really easy to implement (even if it is hard to understand sometimes).

In your code, you just need to change the line:

return -1;

to be:

return -start - 1

Result

Putting all the above together, I would have your function as:

public int binarySearch(final int[] arr, int start, final int length, final int search) {
    if (start < 0 || start >= arr.length) {
        throw new IllegalArgumentException("Invalid start index " + start + " in array of size " + arr.length);
    }

    if (length < 0 || start + length > arr.length) {
        throw new IllegalArgumentException("Invalid length " + length + " in array of size " + arr.length + " and start from " + start);
    }

    int end = start + length - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == search) {
            return mid;
        }
        if (search > arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return -start - 1;
}