Binary Search | Search Algorithm

The theory

A binary search algorithm is a search algorithm that uses the concept of divide and conquer in order to find a target value’s position. Basically, this search algorithm compares the target value with the middle element of the collection.

If it is equal, return the position. If it is not equal, then we will need to check if the value is either greater or less than the target value. This is to know what side of the collection we need to split.

Binary Search Requirements

There’s a condition applied to the binary search array, which is that the array must be sorted. This is because it uses the value (in our case an integer), to compare and check if the selected position has the target value or check where to go.

Implementation

First things first, we will create our binary search class with the search methods.

public class BinarySearch {

    public int search(int[] array, int number) {
        return search(array, number, 0, array.length);
    }

    private int search(int[] array, int target, int start, int end) {
        int mid = (start + end) / 2;

        if (end < start) {
            return -1;
        } 
        
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            return search(array, target, 0, mid - 1);
        } else {
            return search(array, target, mid + 1, end);
        } 
    }
}

You can do the search recursively or with a while loop. I found the recursive way simpler than the other one. Let’s go through the code: the first thing we need is grab the middle position by adding the start (lower/min) and end (high/max) position and dividing by two. We will also need a check if it the end position is lower than the start to avoid any exception, which also means that the target was not found.

After doing the previous check, we starting comparing if the value in the middle position equals the target, returning mid position if it’s true. If it is not, then we check if that value is larger that the target, going to the left side of the array (start: 0, end: mid-1) and tries again. If the value is smaller than the target, then it goes to the right (start: mid+1, end: previous end value).

This will be the logic behind the search method, going recursively through the array until we find the position or return -1 if it did not find the target. Now let’s create our main method in order to test our implementation:

    private static int[] array = {4,8,12,16,20,24,28,32};
  
    public static void main(String[] args) {
        BinarySearch search = new BinarySearch();
        System.out.println(search.search(array, 12));
    }

The output should print 2. We have finished implementing a binary search algorithm. Please let me know if you have any questions or you just want to comment something.