Given a sorted array of unique nums and a key, find the key index if present. If not, return the index where it would be if inserted in order.

Consider a **sorted** input of **unique** elements`[1,3,4,5,9,10]`

that we need to analyze to find the insertion location for a `key`

, say **7**. As clear from the input, the key is not present in the input and, if added, should be added at index **4** (0 based) to maintain the sorted nature of the input.

Also, as the input contains unique elements, we will return the existing index if the key is already present in the input array.

The brute-force approach will use linear search, where we simply iterate the input array and compare the key with every array element.

- If the
`key`

is found in the`input`

, return its`index`

. - else, If the last element is smaller than the key, return
`lastIndex + 1`

- otherwise, return the
**first index**containing a value more than the key.

The worst-case complexity of this solution will be \(O(n)\) as we might end up traversing the complete input.

A better way to solve this problem is to use a variant of binary search where instead of returning a default value in case the key is unavailable, we return the index where it should be inserted, ensuring the sorted nature of the input. Let’s take a look at the following implementation:

```
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end){
int mid = start + (end - start) / 2;
if(nums[mid] == target){
return mid;
}
if(nums[mid] < target){
start = mid+1;
} else{
end = mid - 1;
}
}
return start;
}
```

As mentioned above, the algorithm will iterate over the input as long as \(start \leq end\). For the scenario where the `key`

is not present in the input, it will go till both start and end point to the same `element`

before terminating the loop.

Now, if the `key`

is smaller than the `element`

, the else part will execute, and via `end = mid - 1`

, **end** will be updated, causing the loop to terminate. But as **start** still points to the smallest value greater than `key`

, it represents the correct index where `key`

should be inserted.

On the other hand, if the `key`

is more than the `element`

(largest value smaller than the key), the **start** index will be updated by `start = mid+1`

, causing the loop to terminate as \(start \leq end\) is no longer valid. Now start points to 1 position to the right of the `element`

, again the correct position for inserting the key and ensuring the sorted nature of the input.

The overall complexity of this algorithm remains as of binary search i.e. \(O(log_2n)\)

Be notified of new posts. Subscribe to the RSS feed.