JavaImplementation of basic algorithms

Binary search in Java

Remember, the binary search is a fast algorithm for finding the position of an element in a sorted array. The algorithm runs in at work logarithmic time, making O(log n) comparisons where n is the length of the input array.

It begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than or greater than the middle element, the search continues in the left or right subarray, respectively, eliminating the other subarray from consideration. It repeats until the value is found or a new search interval is empty.

Let's implement this algorithm in Java using a while loop and recursive calls.

The iterative implementation

Despite the fact that the main idea of the binary search looks very simple, the implementation requires some caution with array indexes and conditions.

1) The iterative implementation uses a loop for iterating over the passed array. If the considered interval is empty the loop stops and the method returns -1 that indicates the element is not found.

public static int binarySearch(int[] array, int elem, int left, int right) {

    while (left <= right) {
        int mid = left + (right - left) / 2; // the index of the middle element
            
        if (elem == array[mid]) {
            return mid; // the element is found, return its index
        } else if (elem < array[mid]) {
            right = mid - 1; // go to the left subarray
        } else {
            left = mid + 1;  // go the the right subarray
        }
    }
    return -1; // the element is not found
}

The method takes an array of int's, a target element and two boundaries of the subarray where we search the element. The last two parameters are not necessary but they are useful if we also want to be able to search not in the entire array.

Let's test the method passing an array with the same numbers as we have already considered above.

int[] array = { 10, 13, 19, 20, 24, 26, 30, 34, 35 };
        
int from = 0, to = array.length - 1;
        
int indexOf10 = binarySearch(array, 10, from, to); // 0
int indexOf19 = binarySearch(array, 19, from, to); // 2
int indexOf26 = binarySearch(array, 26, from, to); // 5
int indexOf34 = binarySearch(array, 34, from, to); // 7
int indexOf35 = binarySearch(array, 35, from, to); // 8
        
int indexOf5 = binarySearch(array, 5, from, to);   // -1
int indexOf16 = binarySearch(array, 16, from, to); // -1
int indexOf40 = binarySearch(array, 40, from, to); // -1
If we call the method with other borders for the same array, the results will be different.
int from = 0, to = 2;
        
int indexOf10 = binarySearch(array, 10, from, to); // 0
int indexOf19 = binarySearch(array, 19, from, to); // 2
int indexOf26 = binarySearch(array, 26, from, to); // -1
int indexOf34 = binarySearch(array, 34, from, to); // -1
int indexOf35 = binarySearch(array, 35, from, to); // -1

The recursive implementation

2) The recursive implementation makes a recursive call instead of using a loop. It doesn't throw the StackOverflowError because it makes not many recursive calls even for large arrays.

public static int binarySearch(int[] array, int elem, int left, int right) {

    if (left > right) {
        return -1; // search interval is empty, the element is not found
    }
        
    int mid = left + (right - left) / 2; // the index of the middle element
        
    if (elem == array[mid]) {
        return mid; // the element is found, return its index
    } else if (elem < array[mid]) {
        return binarySearch(array, elem, left, mid - 1); // go to the left subarray
    } else {
        return binarySearch(array, elem, mid + 1, right); // go the the right subarray    
    }
}

Make sure that the method returns the same results as the previous one.

In fact, iterative and recursive implementations are equivalent. Use any of them for educational purposes. But remember, the binary search is implemented in the Java standard library, see java.util.Arrays.binarySearch(...) for details. It works for different data types including integer numbers, characters, strings and so on.

Ways to calculate the index of the middle element

There are different ways to calculate the middle element:

  • The simplest one is sum both borders and divides them by two:
int mid = (left + right) / 2;

But this simple formula has one disadvantage - It fails for large values of left and right when the sum is greater than the maximum positive int value. The sum overflows to a negative value, and the index will be negative when divided by two.

  • The longer formula protects us from the int overflow. We used it in our binary search implementations.
int mid = left + (right - left) / 2;

Actually, it's the same as the previous formula but protects us from the int overflow.
left + (right - left) / 2 = (2 * left + right - left) / 2 = (left + right) / 2

  • Using a bitshift operator:
int mid = (left + right) >>> 1;

When we sum left and right we may get a negative value because of the type overflow, but the unsigned right shift operator processes the value correctly. Also, it may be faster than the division.
2 learners liked this piece of theory. 2 didn't like it. What about you?
Report a typo