Interview question: Binary search in a sorted array

One of the questions that will usually come during an interview is related to Big O notation. This is a way for them to see how well you understand the efficiency or resource consideration of a particular algorithm. More importantly, they may be looking to see if you know how to implement a method using different variations of Big O. In this post I’ll show you 2 ways that you can implement a binary search on a sorted array.

Usually the question is presented to you like this; you’re given a sorted array of integers, what’s the best way to find if an integer is within the array? Simply starting from one end and moving towards the other incrementally is O(n). This would be fine except the hint that the array was sorted. Being sorted indicates that you use the divide and conquer method of binary search.

Now you have to decide whether to implement it by recursion or by iteration. Both have their advantages and disadvantages (which you should discuss with the interviewer). Personally, being taught C++ as my first real programming language (sorry BASIC!), I try to avoid recursion when possible. I know that in managed languages like Java and C# stack overflows are not as much of a worry as they are with native languages, but I generally feel that loops are a much safer way of programming. Other things to keep in mind when deciding which method to use are readability and maintenance. I’m sure you can write hotshot code for either one, but will you be able to easily understand what you wrote a year from now when you’re debugging a problem involving your chosen method? Or when someone else takes over your code because you’ve moved onto another project\team? Keep these in mind when deciding upon a method.

With either method the core logic is going to be the same for this task. First we will want to find the lowest and highest array indices. These will be used to determine the initial search location. If the location is not the value we’re searching for, we adjust the minimum or maximum index allowing for the first division of the data. The code will look something like this.

// Checking if the location is valueToFind
currentPos = (maxPos + minPos) / 2;
if (sortedArray[currentPos] == valueToFind)
   return true;

// Calculating a new minPos or maxPos values
if (sortedArray[currentPos] < valueToFind)
   minPos = currentPos + 1;
else
   maxPos = currentPos - 1;

If we’re using iteration we’ll want to keep looping through the core logic while the minimum index is less than or equal to that of the maximum or the value is found.

// Searching for valueToFind in sortedArray
while (minPos <= maxPos) {

   // Checking if the location is valueToFind
   currentPos = (maxPos + minPos) / 2;
   if (sortedArray[currentPos] == valueToFind)
      return true;

   // Calculating a new minPos or maxPos values
   if (sortedArray[currentPos] < valueToFind)
      minPos = currentPos + 1;
   else
      maxPos = currentPos - 1;
}
        
// valueToFind is not in the array
return false;

Similarly with the recursion, the method will continue calling itself until either the value is found or the maximum index is less than that of the minimum.

// Check if the location is valueToFind
int currentPos = (minPos + maxPos) / 2;
if (sortedArray[currentPos] == valueToFind)
   return true;

// Calculating a new value for minPos or maxPos
if (sortedArray[currentPos] < valueToFind)
   minPos = currentPos + 1;
else
   maxPos = currentPos - 1;

// If the new maxPos is less than minPos, we know valueToFind is not in the array
if (maxPos < minPos)
   return false;

// Trying new location since valueToFind was not in the current one
boolean findResult = RecursionMethod(valueToFind, sortedArray, minPos, maxPos);
return findResult;

All right, let’s talk test cases. We should come up with some scenarios that verify the logic in-depth. We’ll want to search for values that are less\greater than the lowest\highest value in the array, search for values not in the array but would fall between values that do exist, and interesting array sizes. Interesting array sizes would include a null array, a single element because the minPos and maxPos values are the same, and an array with 5 elements because it‘s the simplest tree with an odd number of elements that require both the minPos and maxPos to change to find at least 1 value, and finally 6 elements because it’s the simplest tree with an even number of leafs that require both minPos and maxPos to change to find at least 1 value in the array.

And there you have it! A binary search algorithm on a sorted array with interesting test cases. Understand this and when it comes up in an interview you’ll breeze through it.

You can view the full source code here.