# Binary Search for Technical Interviews

Binary search algorithm is a widely used searching algorithm to find data in a sorted collection.

Binary search is also referred to as half-interval search. If you can, roughly, eliminate half of the search area with a condition (invariant), you can use binary search to find the target solution.

The algorithm runs in O(log n) in worst and average cases, making it efficient for solving many search-related problems.

You can implement it iteratively or recursively. In this article, you will use iterative implementation to have O(1) space complexity.

The primary examples of binary search usage show how to implement it and find some data in a sorted collection. However, the algorithm can be used in more complicated scenarios.

For example, the algorithm can be used to solve the following problem types:

• find the maximum element not greater than x (leftmost element)
• find the minimum element not less than x (rightmost element)
• find the kth element
• minimax problems
• maximize/minimize the arithmetic mean of a subset with some properties

At the first look, binary search can be straightforward to implement. However, the real-world usage showed the opposite.

“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky”. — Donald Knuth

The famous issue with a tricky implementation related to number overflow when calculating a middle point `(left + right) / 2`. The problem affected many textbooks and programming language implementations.

If you are interested to learn more about the overflow issue, check the Google research blog Nearly All Binary Searches and Mergesorts are Broken which shows details of that problem.

Also, common issues with using binary search to solve interview problems are related to edge cases such as:

• left pointer is pointing to the solution
• right pointer is pointing to the solution
• pointer is out of the collection range
• the invariant doesn’t cover rare inputs

It’s critical to understand and be able to implement variations of binary search depending on the problem you need to solve.

In this article, you will learn how to implement binary search and use it to solve real interview problems.

## Binary Search Implementation

Before solving problems, you need to understand how binary search works and implement the algorithm.

For the explanation, I will use pseudocode and, for problems solution Rust, but the implementation would be similar to other programming languages.

First, you need to have a sorted collection or, in more complicated scenarios sorted slice (subcollection). A collection can be sorted in ascending on descending order. The order will impact conditions where you should move `left` and `right` pointers.

The search starts by comparing elements in the `middle` of the collection with the target value.

To find the middle use `middle = left + (right - left) / 2`. This formula calculates the middle point and is a safe way of doing it. It will protect you from having an overflow issue.

The `left` pointer initially holds zero as an index, and the `right` pointer takes the collection size.

``````left = 0;
right = arr.len();
``````

In many problems you may see that `left` and `right` pointers are pointing outside of the collection or represent the search space for the problems not related to arrays.

Setting `left` and `right` pointers outside the collections can be helpful in some cases and may simplify the code, but you have to be careful when accessing the collection values using `left` and `right` pointers. If they point to values that are not valid indexes(collection bounds), you will get an index out of bounds error.

``````left = -1
right = arr.len()
``````

When you calculate the `middle` value, compare it with the target value, and if it matches, you have found the seeking value.

``````if arr[middle] == target { return middle }
``````

If the `arr[middle] < target` satisfies, the search continues in the right half of the collection; otherwise, it searches in the left half.

``````if arr[middle] < target {
left = middle + 1
} else {
right = middle
}
``````

On each iteration, the algorithm eliminates half of the collection in which the target value can’t be found.

``````left = 0
right = arr.len()

while left < right {
middle = left + (right - left) / 2

if nums[middle] == target {
return middle
}

if arr[middle] < target {
//the searched value in the right part
left = middle + 1
} else {
// the searched value in the left part
right = middle
}
}

return -1
``````

The algorithm steps can be summarised as follows:

• The `left` pointer points to the `0` index (in most cases)
• The `right` pointer points to the collection size
• The `while` loop condition is `left < right`
• Move the `left` or `right` index to the `middle` index

Note that the above binary search implementation is one of the many possible implementations. Of course, not every problem can be solved with one common pattern, but when you try to consider the specifics of each problem, you can easily fail with tricky edge cases.

The next step is to apply your knowledge to solve frequently-asked binary search problems.

## Binary Search Problems

Many binary search problems are written in a way that, on the first look, it’s not clear when binary search can be used. The complexity can be defining a search condition or even doing unrelated to binary search manipulations to transform the input data before applying binary search. However, pay attention to small details. When you see a problem that requires a solution with `O(log n)` or sequence is sorted or can be sorted, this can be a good indicator of possible binary search usage.

Alright, let’s try to solve some binary search problems. I would encourage you to solve them on your own and then check the solution.

### Find First and Last Position of Element in Sorted Array

Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value.

If `target` is not found in the array, return `[-1, -1]`.

You must write an algorithm with `O(log n)` runtime complexity.

Source: Leetcode

#### Solution

To solve this problem, you first need to solve two subproblems. The solution to the subproblems will be the solution to the main problem.

The subproblems are:

• find the leftmost element (`lower_bound`)
• find the rightmost element (`upper_bound`)

To find `lower_bound`, you can use binary search algorithm to return `left` index. After search completion, it’s guaranteed that the `left` pointer will point to a seeking target element if the element exists.

``````pub fn lower_bound(nums: &[i32], target: i32) -> i32 {
let mut l = 0;
let mut r = nums.len();

while l < r {
let m = l + (r - l) / 2;

if nums[m] < target {
l = m + 1;
} else {
r = m;
}
}

l as i32
}
``````

Finding `upper_bound` can be tricky. The array is sorted in non-decreasing order, meaning that we need to find an element from the right side. You need to change the pointer moving condition to find the rightmost element.

If the `middle` element is greater than the target, you move `right` to the `middle` and continue searching on the left part. Otherwise, on the right part.

``````if nums[m] > target {
r = m;
} else {
l = m;
}
``````

When the loop `while l + 1 < r` completes, the `left` and the `right` pointers will hold the indexes of the adjacent elements, and the `left` pointer value is the rightmost element’s index.

``````pub fn upper_bound(nums: &[i32], target: i32) -> i32 {
let mut l = 0;
let mut r = nums.len();

while l + 1 < r {
let m = l + (r - l) / 2;

if nums[m] > target {
r = m;
} else {
l = m;
}
}

l as i32
}
``````

Now, when you have functions to find `lower_bound` and `upper_bound` you can use them to find the final result.

``````let l = lower_bound(&nums, target);
let r = upper_bound(&nums, target);
``````

The `left` index from the `lower_bound` function result can be outside the array length or point to a not-target array element. To prevent out of index error and check if the target value exists, you need to check if `left` is in the array size bounds and `nums[l] != target`. If any of those conditions are true, return `[-1, -1]`.

``````if l == size || nums[l as usize] != target {
return vec![-1, -1];
}
``````

The completed solution code.

``````pub fn lower_bound(nums: &[i32], target: i32) -> i32 {
let mut l = 0;
let mut r = nums.len();

while l < r {
let m = l + (r - l) / 2;

if nums[m] < target {
l = m + 1;
} else {
r = m;
}
}

l as i32
}

pub fn upper_bound(nums: &[i32], target: i32) -> i32 {
let mut l = 0;
let mut r = nums.len();

while l + 1 < r {
let m = l + (r - l) / 2;

if nums[m] > target {
r = m;
} else {
l = m;
}
}

l as i32
}

pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
let size = nums.len() as i32;

if size == 0 {
return vec![-1, -1];
}

let l = lower_bound(&nums, target);
let r = upper_bound(&nums, target);

if l == size || nums[l as usize] != target {
return vec![-1, -1];
}

vec![l, r]
}
``````

### Search in Rotated Sorted Array

There is an integer array `nums` sorted in ascending order (with distinct values).

Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (0-indexed). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`.

Given the array `nums` after the possible rotation and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`.

You must write an algorithm with `O(log n)` runtime complexity.

Source: Leetcode

#### Solution

In this problem, the `nums` array possibly can be rotated, meaning you will have two sorted chunks. The adjacent elements, after rotation, will form a peak and drop. If you find the peak, you can apply binary search on the left and the right parts of the peak to find the target value.

So how do you find the peak value? If the array is sorted in ascending order, it means the value `nums[m]` is greater than `nums[m - 1]`, and if the sequence is without rotation, the most left value is less than `nums[m]`. If the most left value ( `nums[l]`) is greater than `nums[m]` means that the peak value is in the left part; otherwise in the right part.

``````let size = nums.len();

let mut l = 0;
let mut r = size;

while l + 1 < r {
let m = l + (r - l) / 2;

if nums[m] > nums[m - 1] && nums[m] > nums[l] {
l = m;
} else {
r = m;
}
}

let pivot = l;
``````

After finding the peak value (pivot), the problem is reduced to finding the element in the subarray from the left part of the pivot and the right part.

``````&nums[0..=pivot]
&nums[pivot + 1..]
``````

To find the target element, you can implement binary search, but in Rust, you can use a standard implementation, which will simplify the code.

``````if let Ok(idx) = &nums[0..=pivot].binary_search(&target) {
return *idx as i32;
}

if let Ok(idx) = &nums[pivot + 1..].binary_search(&target) {
return (*idx + l + 1) as i32;
}
``````

If the target element is found on the left or right part, return it index.

The completed solution code.

``````pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let size = nums.len();

let mut l = 0;
let mut r = size;

while l + 1 < r {
let m = l + (r - l) / 2;

if nums[m] > nums[m - 1] && nums[m] > nums[l] {
l = m;
} else {
r = m;
}
}

let pivot = l;

if let Ok(idx) = &nums[0..=pivot].binary_search(&target) {
return *idx as i32;
}

if let Ok(idx) = &nums[pivot + 1..].binary_search(&target) {
return (*idx + l + 1) as i32;
}

-1
}
``````

## Wrapping up

Binary search is an efficient search algorithm and can be used to solve various problems. Still, you need to be able to evaluate possible edge cases and adapt binary search implementation to find the desired solution.

Luckily, you have a lot of free resources to practice binary search problems.

Leetcode provides the study plan and the collection of binary-search problems.

You also can try to solve competitive programming problems from Codeforces related to binary search. Remember that Codeforces problems can be tough to solve and require knowledge from different topics that are not covered in this article.

Don’t be discouraged when you cannot solve any of the problems. Leetcode problems with an easy tag don’t mean they are easy.

Keep practicing, and eventually, the problems you saw hard to solve become obvious to you.

Originally published at https://medium.com/@almmiko