Let’s take a look at a problem on leetcode.com, an algorithm challenge by the name of Solving Search Insert Position Algorithm. Here, we have an algo that requires us to check and manipulate an array in a way that can be tricky, so let’s check it out!
The Problem
As pictured above, our goal is to write a function that takes in a sorted array and a target value and returns the index of the value in the array, or the trickier part, the index where the value should be if placed in order. So if we have an array of [1,3,5,6] and a target of 5, we return the index 2. If the target is 2with that same array, we would return 1, since we would place it between 1 and 3 at the second index spot.
The Solution
Firstly, if the array has the target inside of it, that’s an easy solution. We can just put a base-case at the start that checks the array for the target, and then returns the index if true. Easy-peazy.
Next, because we’re working with a sorted array and we’re looking for a specific location in the array, we can use a binary search to improve our efficiency. We’ll create two integer variables, start and end (start initializing at 0, end initializing as the last index of our array), and while start is less than end, we will go through our binary search. We’ll create a variable, mid, and define it as the rounded down average of our start and end values. Then, we will check our mid value against the target value. If it is greater than, we move our end to the mid-1 and start over. If it is less than, we move our start value to mid+1 and repeat. We do this until we find the final spot that our target should be. However, this breaks if the target should be placed at the very end of the array. Considering this, we set up a ternary operator to return either the found index or our final start value, which by that point should be 1 greater than our original end value. Our final product looks like this:
Hope this was helpful! Keep practicing those algos!
