Binary Search In Java: Examples And Interview Tips

I recommend following along with my video if you want to see some examples and hear step by step how I coded binary search in Java!

A few years ago, I was interviewing for a software engineering internship at a large tech company. I was asked a question and was able to implement the first part with ease. The interviewer followed up on that and asked me to code binary search. I remembered learning binary search in my data structures and algorithms course, but I could not remember how to code it. I frustratingly spent the next 25–30 minutes trying to remember how to code it.

That was the day binary search became one of my must know algorithms for coding interviews. I learned that day that not knowing what binary search is or how to code it could cost you a job offer. To make sure none of you repeat my mistake, we will be going over what binary search is, how you code binary search in Java, and I’ll give tips on how binary search might come up in coding interviews. If this post is helpful, please consider subscribing to my YouTube channel or following me on Hackernoon for more content like this!

Binary Search Explained

Before we talk about binary search, it is important we understand the alternative: linear search. In linear search, we go through a list one element at a time, starting from the first element. We check if each value is the target value we are looking for. In the worst case, we go through the entire list, so this has an O(n) time complexity (don’t worry if you haven’t learned Big-O yet, it’s not necessary to understand binary search).

Binary search improves on this but has two prerequisites. First, your input must have random access in O(1) time. This means we can access any element in our data structure in O(1) time. For this, we commonly use an array. Second, the input must be sorted. Once we’ve met those prerequisites, we’re ready to use binary search!

With binary search, instead of starting at the first element in the array, we instead start in the middle. We check if that value is the target value. If it is, then we have found the number in our array. If the value is greater than our target value, we no longer need to consider it and all values to the right (at a greater index) because they are all larger than the middle value (this is why the input must be sorted).

If the value is less than our target value, then we no longer need to consider it and all values to the left (at a lesser index) because they are all lesser than the middle value. We then repeat the algorithm on the portion of the array we are still considering.

Binary Search Java Code

Here is how you implement binary search recursively in Java:

/**
 * Performs binary search for num on arr recursively
 * @param arr is the input array that we are performing binary search on
 * @param num is the number we are searching for in arr
 * @return the index of num in arr or -1 if num is not present in arr
 */
public int binarySearch(int[] arr, int num) {
    // If array is empty, the element does not exist
    if (arr.length == 0) {
        return -1;
    }
    return binSearchHelper(arr, num, 0, arr.length - 1);
}

/**
 * Helper method for binary search
 * @param arr is the input array that we are performing binary search on
 * @param num is the number we are searching for in arr
 * @param low is the lowest index we are still considering
 * @param high is the highest index we are still considering
 * @return the index of num in arr or -1 if num is not present in arr
 */
private int binSearchHelper(int[] arr, int num, int low, int high) {
    // If only one index left to consider
    if (low == high) {
        return arr[low] == num ? low : -1;
    }

    // Start in the center of the portion of the array we are considering
    int mid = low + ((high - low) / 2);
    if (arr[mid] < num) {
        // All elems to the left of index mid in arr are lesser
        return binSearchHelper(arr, num, mid + 1, high);
    } else if (arr[mid] > num) {
        // All elems to the right of index mid in arr are greater
        return binSearchHelper(arr, num, low, mid - 1);
    } else {
        // We found num
        return mid;
    }
}

Here is how you implement binary search iteratively in Java:

/**
 * Performs binary search for num on arr iteratively
 *
 * @param arr is the input array that we are performing binary search on
 * @param num is the number we are searching for in arr
 * @return the index of num in arr or -1 if num is not present in arr
 */
public int binarySearch(int[] arr, int num) {
    // If array is empty, the element does not exist
    if (arr.length == 0) {
        return -1;
    }

    // The lowest and highest indices we are still considering
    int low = 0;
    int high = arr.length - 1;

    while (low != high) {
        int mid = low + ((high - low) / 2);
        if (arr[mid] < num) {
            low = mid + 1;
        } else if (arr[mid] > num) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    // If only one index left to consider
    return arr[low] == num ? low : -1;
}

Binary Search in Interviews

There are three key things that you should keep in your mind when you’re considering using binary search in a coding interview.

1. If your input is not sorted, only use binary search if your time complexity is worse than O(n*log(n)). This is because the worst case time complexity for the most optimal comparison-based sorting algorithms (like merge sort) is O(n*log(n)). Therefore, if you have a time complexity of O(1), O(n), or O(n*log(n)), you won’t get any value from using binary search if your input is not sorted.
2. Think about whether you can use binary search in cases where you are using linear search. It is in these cases that we may be able to replace that linear search lookup with binary search.
3. Pay close attention to the constraints that the interviewer gives to you. If the input to your problem is sorted, there is usually a reason why. This should immediately make you think about whether you can use binary search as part of your solution.

I hope you found this story informative! Please share it with a friend you think might benefit from it as well! If you liked the post/video, feel free to leave a clap/like and follow/subscribe to my YouTube account for more content like this. Also, follow me on Twitter for updates on when I am posting new content. I hope to see you all on the next one!

Previously published at https://levelup.gitconnected.com/binary-search-cbc0c4ed72f5