What Is Binary Search?

Learn what binary search is and how we can implement it.

We'll cover the following

Binary Search (BS) is one of the most basic searching algorithms. It is common for interviewers to ask coding questions where the only or optimal solution requires us to use binary search. . This is especially important at on-site interviews, where interviewees are asked only two to four different problems. Unfortunately, failure to effectively use binary search bug-free can be a red flag.

Binary search is also referred to as half-interval search, which gives us a hint at when to use it. If we can, roughly, eliminate half of the search area with a single condition, then we are binary searching our target.

Handling Corner Cases!

The most common reason why candidates fail at binary search coding interview questions is that they fail to handle corner cases.

There are many reasons why binary search corner cases might form. For instance, a corner case is formed when the target is at the 0th index of an array when the target is at (n - 1)th index, when the loop goes infinite, and so on.

Luckily, these pitfalls can be avoided if we choose the same approach every time.

Now, we will take a walk through this approach.

One universal approach

1. Pattern

This is a unique form of binary search. It uses the current index and its immediate left and right neighbors’ indices in the array.

Let’s list the essential points of the algorithm and understand each one of them.

left = 0
right = size of array
while (left + 1 < right)
  mid = (left + right) / 2
  if (array[mid] == target)
    return mid
  else if (array[mid] < target)  
    continue search in right side  
  else  
    continue search in left side
if (array[left] == target)
  return left
return -1

Let’s list the essential points of the algorithm and understand each one of them.

  • Line 1: We take 0 as our left index.

  • Line 2: We will take the size of the array as our right index. Hence, we will need to be careful with the right one when we check the item on this index.

  • Line 4: The while loop finishes when there is no element between the left and right ones. Thus, if there is one element in the array, we will skip the loop.

  • Line 14: We must check the element on the left index outside the loop because if we skip the loop, it can become the target.

2. Implementation

Here is the code for our approach:

#include <iostream>
#include <vector>
using namespace std;
int searchInsert(vector<int>& nums, int target) {
  // the initial value for left index is 0
  int left = 0;
  // the initial value for right index is the number of elements in the array
  int right = nums.size();
  // left + 1 >= right will finish while loop
  while (left + 1 < right) {
    int mid = (right + left) / 2;
    
    if (nums[mid] == target) {
      // mid is the index of the target
      return mid;
    } else if (nums[mid] < target) {
      // there is no sense to search in the left half of the array
      left = mid;
    } else {
      // there is no sense to search in the right half of the array
      right = mid;
    }
  }
  // left can be the index of the target
  if (nums[left] == target) {
    return left;
  }
  // the target doesn't exist in the array
  return -1;
}
int main() {
  vector<int> nums = {1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
  cout << "Index of 37 is ---> " << searchInsert(nums, 37) << endl;
  cout << "Index of 1 is ---> " << searchInsert(nums, 1) << endl;
  cout << "Index of 59 is ---> " << searchInsert(nums, 59) << endl;
  cout << "Index of 25 is ---> " << searchInsert(nums, 25) << endl;
  return 0;
}
BS basic implementation

Here is a visual representation of our algorithm, in a general case where 37 is a target:

Let’s check the steps that our algorithm takes to handle corner cases:

  • The target is the first element in our array.
  • The target is the last element in our array.
  • The target doesn’t exist in our array.

3. Details

Most of the people who deal with binary search problems get stuck by considering the specifics of each problem. But, most binary search questions rely on the same concepts. If we use the same solid foundation for our solution, we can easily bypass all of the specifics.

Our foundation is built on five simple points:

  • The left index points to 0 index.
  • The right index points to the size of array.
  • The while loop condition is left + 1 > right.
  • We will move the left or right index to the mid index.
  • We will check an element on the left index, outside of the loop.

Let’s take a look at the complexity of our approach in the next lesson.