LeetCode problem #35 — Search Insert Position (JavaScript)

In this LeetCode problem, we’re given an array of ordered integers, and a target integer, and asked to return the index of where the target can be found in the array. If the target cannot be found in the array, we’re asked to return the index of where it would be found if it were added.

The basic idea behind solving this problem is to look for the first occurrence in the array that is greater than or equal to the target number. So that’s what we’ll do below, in two different ways.

Solution #1: The for loop

The brute-force approach here is to do more or less exactly what is described above. We loop through the array’s values, looking for the target. If we find either the target, or the first occurrence of an integer higher than the target one (which indicates that that’s where the target would be located), we return the index.

The downside of this simple solution is that we have to check every number in the array in order to get our answer.

Solution #2: Binary search

To speed things up, we can employ the use of a fairly standard binary search. The search will half the available array, look for which side’s range of values contains the target (or integers higher than it), and then discards the other side, before repeating the process. This means we keep cutting down the array, checking as little data as possible each time, until we’re left either with the target integer, or the next highest number from it, giving us our answer.