What you need to understand before you start preparing for a Coding Interview

Binary Search patterns

This is the first article where we cover two patterns: Classic Binary Search and Boundary Binary Search

 

In the classical sense, Binary Search is a pattern that allows us to find a number in a sorted array very quickly. On the one hand, this is absolutely correct, but this definition significantly narrows the range of problems where the pattern can be used.
The Binary Search pattern can be divided into four main variations. Finding a target in a sorted array is Classic Binary Search. The other three represent more advanced ways of applying the Binary Search pattern.

 

Classic Binary Search aproach is one of the most fundamental search patterns in algorithms. It is used to find a specific target value in a sorted collection by repeatedly dividing the search space in half.
Instead of checking every element one by one, Binary Search compares the target with the element in the middle of the current search range. Based on this comparison, one half of the remaining elements can be safely discarded.
Classic Binary Search pattern

A common C++ implementation looks like this:

int left = 0;
int right = nums.size() - 1;

while(left <= right)
{
  int mid = left + (right - left) / 2;

  if(nums[mid] == target)
    return mid;

  if(nums[mid] < target)
    left = mid + 1;
  else
    right = mid - 1;
}

return -1;

Because the remaining search space is divided approximately in half after every iteration, the time complexity is O(log n). The iterative implementation uses only a few variables, so the space complexity is O(1).

 

Typical LeetCode problems that demonstrate Classic Binary Search include:

 

34. Find First and Last Position of Element in Sorted Array
35. Search Insert Position
278. First Bad Version
374. Guess Number Higher or Lower
704. Binary Search

 

Boundary Binary Search is a variation of Binary Search used when we are not looking for just any occurrence of a value, but for the exact position where a condition changes - for example, the first or last element that satisfies a particular condition.

 

The main recognition clue is:

 

We need to find the first or last position where a condition becomes true.

 

Instead of thinking about individual values, it is useful to imagine the search space as a sequence of false and true values:

false false false true true true 
                 ↑ 
              boundary

Once the condition becomes true, it remains true for every element to the right because the array is sorted.

Boundary Binary Search pattern

A common C++ implementation looks like this:

int left = 0;
int right = nums.size() - 1;
int answer = nums.size();

while(left <= right)
{ 
  int mid = left + (right - left) / 2;
  if(nums[mid] >= target)
  {
    answer = mid;
    right = mid - 1;
  }
  else
  { 
    left = mid + 1; 
  }
}

return answer;

The important difference from Classic Binary Search is that finding a valid element does not necessarily end the search. You save it as a possible answer and continue searching toward the required boundary.

The same idea can be reversed to find the last valid element, the first occurrence of a target, or the last occurrence of a target.

Because half of the remaining search space is eliminated at every step, the time complexity is O(log n) and the iterative implementation uses O(1) extra space.

 

Typical LeetCode problems that demonstrate Boundary Binary Search are:

 

34. Find First and Last Position of Element in Sorted Array
35. Search Insert Position
69. Sqrt(x)
278. First Bad Version
744. Find Smallest Letter Greater Than Target

© 2026 Algobytes