How to think in an advanced Binary Search problem

In this article, I will go over one of my favorite binary search problems. We are given a target to find and an array where the numbers are firstly increasing and then decreasing. Find the index of the target in the array. The target appears only once in the array. If there is no target found, we could return -1.

How to think

Because we see there is some sort of ordering and we need to find something our brains should immediately jump to binary search. Binary Search is often associated with an array where numbers are either increasing [1, 4, 8, 56, 105] or decreasing [45, 34, 13, 7, 5, 3, -9]. But what changes if an array is firstly increasing and then decreasing? The answer is nothing changes but we need to recognize the pattern! If we knew where the array switched from increasing to decreasing then we could just simply do a normal binary search on the increasing part and then a binary search for a descending array on the second part for a run time of O(2 * log N) or just O(log N). So, we can break this problem down into 3 subproblems.

1. Find the peak (the real challenge here).
2. Normal binary search on increasing side (easy).
3. Descending binary search on decreasing side (easy).

Find the peak

The first step would be to find the peak, which is a separate problem itself. When we know where the peak is we can think of this array as two separate arrays with increasing and decreasing patterns.

To find the peak the simplest way we could iterate through the given array, keep track of the highest number, and save its index. In this case, the time complexity would be O(N) and space complexity would be O(1) since we are not creating any additional data structure.

function findIndexPeak(array) {
let highest = 0;
let indexOfHighest = 0;
for (let i = 0; i < array.length; i++) {
if (array[i] > highest) {
highest = array[i];
indexOfHighest = i;
}
}
return indexOfHighest;
}

But can we make it better? Finding the peak in O(N) would be our bottleneck for the whole problem since the other parts are in O(logN). The next fastest time complexity after O(N) is O(log N) which hints on a binary search. Here we need to think a little bit outside of the box to find the peak with binary search. The basics of a binary search are to continuously split a search area in half until we reach what we are looking for. Finding the middle point is nothing different from what we know, but we will need new conditions to choose left or right.

When do we stop? When both right and left numbers from the middle number are less than the middle number.

When do we move the left pointer to the middle? When the left number from the middle point is less and the right number is more than the middle.

When do we move the right pointer to the middle? When the left number from the middle point is more and the right number is less than the middle.

We can keep performing this operation until we find the peak!

These three questions are the questions you should ask yourself in order to solve any O(log N) or binary search problem. A lot of times it won’t be as simple as just finding a number in a sorted array but if you can break it down to these three conditions the problem will basically be that simple.

function findIndexPeak(array) {
let left = 0;
let right = array.length - 1;
let mid;
while (left < right) {
mid = Math.floor(left + right) / 2;
if (array[mid-1] < array[mid] && array[mid] > array[mid+1]) {
return mid;
}
else if(array[mid-1] < array[mid] && array[mid] < array[mid+1]) {
left = mid;
} else {
right = mid;
}
}
}

Now that we have the peak, we have two parts of the array with increasing or decreasing patterns. The rest is the easy part and should mainly be a refresher. Because our target could be on either side of the peak we must be ready to perform the binary search on both sides. The binary search we have to do on each side is a little different because of their orderings. While it would be just fine to have two different binary search functions, instead, to reduce duplicated code we will have one function that can handle both. To differentiate when to use increasing or when to use decreasing we can pass in a flag.

function binarySearch(array, target, left, right, isIncreasing) { 
let mid;
while (left <= right) {
mid = Math.floor((left + right) / 2);
if (array[mid] == target) {
return mid;
}
else if (array[mid] < target) {
if (isIncreasing) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
if (isIncreasing) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1; //if did not find the target
}

The last step is to use findIndexPeak and binarySearch functions. Now we can use isIncreasing boolean to define rightSide and leftSide. The target could only be found on one side, another side will return -1.

Does rightSide equal to -1? In our case, it does meaning there is no target on the right side. So, let’s return the answer from the left side.

function findTarget(array, target) {  
let last = array.length - 1;
let peak = findIndexPeak(array);
let rightSide = binarySearch(array, target, peak, last, false);
let leftSide = binarySearch(array, target, 0, peak, true);
return rightSide == -1 ? leftSide : rightSide;
}

Take a look at the whole solution!

Written by

Full Stak Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store