Find The Correct Position To Insert a Given Element in An Array in Javascript

This article will cover the algorithm of how to find the correct position to insert a given element into a sorted array in Javascript.

First we will set up two variables: one to hold the potential index of the element, and a boolean value to reflect whether we have found the potential index yet. We’ll begin the potential index at 0, and give our second variable, “isFound,” a default value of false.

Now we will begin iterating through our array. First we will check if the target element is equivalent to the element we’ve iterated through. If it is the same, then we want to insert our target element at that index. So we’d set “found” to be the value of the index, and “isFound” to be true. Additionally, if we find the index then we can end our For Loop. So let’s throw a break in there.

Now we need to consider a case where we haven’t found the index after that if statement. We’ll create another For Loop that will take into account when the target element has not been found. In this case, the target would be less than the number we’re iterating over. We’d set “found” equal to that index, and “isFound” equal to true. Then we’d break out of our loop again.

Lastly, we’ll use our “isFound” boolean to decide what to return. If the potential insertion index has been found, then we’ll return that index. Otherwise, our target element should be added to the end of the array.

The Time/Space complexity of this problem will depend on the length of the input array. Therefore, it is O(N).