# Binary Search

Welcome to the binary search series! In this series of post we will focus on implementing binary search for coding interviews and some of the common pitfalls that come along. We will start with the most basic implementation of binary search first.

Before we start coding a solution we want to make that we are aware of all the possible pitfalls in our code. Take a look at the test cases below to get a feel for the scenarios we need to be on the look out for.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public void testEmptyArray() { assertTrue(BinarySearchIterative.binarySearch(new int[]{}, 4) == -1); } public void testOneElementSuccessfulTarget() { assertTrue(BinarySearchIterative.binarySearch(new int[]{2}, 2) == 0); } public void testSuccessfulTarget() { assertTrue(BinarySearchIterative.binarySearch(new int[]{1,2,3}, 2) == 1); } public void testSuccessfulTargetLastElement() { assertTrue(BinarySearchIterative.binarySearch(new int[]{1,2,3}, 3) == 2); } public void testSuccessfulTargetFirstElement() { assertTrue(BinarySearchIterative.binarySearch(new int[]{1,2,3}, 1) == 0); } public void testTargetNotFound() { assertTrue(BinarySearchIterative.binarySearch(new int[]{1,2,5}, 3) == -1); } public void testTargetNotFoundTooLarge() { assertTrue(BinarySearchIterative.binarySearch(new int[]{1,2,3}, 4) == -1); } public void testTargetNotFoundTooSmall() { assertTrue(BinarySearchIterative.binarySearch(new int[]{1,2,3}, -4) == -1); } |

We want to make sure we handle an empty array correctly, an array that doesn’t have the target we seek, an array with one element, and a few other possible edge cases that could come up. Be sure to read through the test. If we don’t address all these possible edge cases then our solution won’t be correct. The solution below addresses all these concerns.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
static int binarySearch(int[] arr, int target) { int l = 0; int r = arr.length; while(l < r) { int mid = l + (r-l)/2; if(arr[mid]==target) { return mid; } else if (arr[mid] > target) { r = mid; } else { l = mid+1; } } return -1; } |

After taking some time to read and understand how this code works, lets focus on a few critical parts of it.

First lets look at how the variable mid is calculated. An alternative is to calculate it this way

1 |
int mid = (l+r)/2; |

However this method can lead to integer overflows so we don’t do it that way.

Next you my wonder why set

1 |
l=mid+1 |

but on the other hand we set

1 |
r=mid |

This is because of integer division in java. Integer division is simply always rounding down we you divide. For example 5/2 = 2 in java. However if we rounded up it would be equal to 3. Why does this matter?

Consider the case when we have an array like so [1,2,3] with a target of 4. When we get to the point in our algorithm where l=2 and r=3 if we set l=mid=2+(3-2)/2 then we would have l=2+0=2. As a result we find ourself in an infinite loop because out terminating condition

1 |
while(l<r) |

would never be met. This is because (3-2)/2=0 would never allow our l variable to increment!

I hope you enjoyed this tutorial on basic binary search. In the next post we will add a variation to the typical binary search algorithm because coding interviews usually wont to see that your comfortable enough with these basic algorithms to handle a twist in them.