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 onsite interviews, where interviewees are asked only two to four different problems. Unfortunately, failure to effectively use binary search bugfree can be a red flag.
Binary search is also referred to as halfinterval 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 = 0right = size of arraywhile (left + 1 < right)mid = (left + right) / 2if (array[mid] == target)return midelse if (array[mid] < target)continue search in right sideelsecontinue search in left sideif (array[left] == target)return leftreturn 1
Let’s list the essential points of the algorithm and understand each one of them.

Line 1: We take
0
as ourleft
index. 
Line 2: We will take the size of the array as our
right
index. Hence, we will need to be careful with theright
one when we check the item on this index. 
Line 4: The
while
loop finishes when there is no element between theleft
andright
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 thetarget
.
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 0int left = 0;// the initial value for right index is the number of elements in the arrayint right = nums.size();// left + 1 >= right will finish while loopwhile (left + 1 < right) {int mid = (right + left) / 2;if (nums[mid] == target) {// mid is the index of the targetreturn mid;} else if (nums[mid] < target) {// there is no sense to search in the left half of the arrayleft = mid;} else {// there is no sense to search in the right half of the arrayright = mid;}}// left can be the index of the targetif (nums[left] == target) {return left;}// the target doesn't exist in the arrayreturn 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;}
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 to0
index.  The
right
index points to the size of array.  The
while
loop condition isleft + 1 > right
.  We will move the
left
orright
index to themid
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.