June 24th 2020

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.

## 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.

- 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.
- 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.
- 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.