# Search Insert Position

## Question ([LC.35](https://leetcode.com/problems/search-insert-position/#/description))

Given a *sorted* array and a target, return the index of the target if it exists or return the index in which target should be inserted.

## Example

```
I: [1,3,5,6], 5
O: 2
I: [1,3,5,6], 2
O: 1
```

## Linear Approach

Scan through the array linearly, find the target or a value bigger than the target

```java
public int searchInsert(int[] nums, int target) {
    // good practice to check null or empty input
    if (nums == null || nums.length == 0) {
        return 0;
    }
    // linear scan
    int i;
    for (i = 0; i < nums.length; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return i;
}
```

This definite works. Can we do better?

## Alternative Approach&#x20;

Construct a binary search tree then search for the lower bound.&#x20;

```python
from sortedcontainers import SortedList 

class Solution:
   
   def searchInsert(self, nums: List[int], target: int) -> int:
       
       sorted_list = SortedList()
       for num in nums:
           sorted_list.add(num)
       
       return sorted_list.bisect_left(target)
       
       
```

## Binary Search Example

Consider this example, given input `[0,2,3,4,6,7,8,11]` find target `6` with the search function below.

```
func search
    Pick a midpoint
    Check if the midpoint is the target, return it if so
    If smaller than the target, we search right section
    If bigger than the target,  we search left section
```

Tracing through this example

```
midpoint = 4, left = [0,2,3], right = [6,7,8,11]
midpoint < target, search right section

midpoint = 7, left = [6], right = [8,11]
midpoint > target, search left section

midpoint = 6, left = [6], right = [6]
return the index of 6
```

If we visualize this array as a binary search tree diagram,

```
               [0-11]
              /     \
    left  [0-3]    [6-11] right
         /    \      /  \
       [0]    [3]  [6] [8-11]
                          /  \
                        [8]  [11]
```

the worst case of going down a path is `log(n)`, where `n` is the size of the input array. Because the binary tree is balanced and we have `2^height = n`, $$height = log\_2(n) = O(log(n))$$.

## Recursive Implementation

A recursive implementation is intuitively sounding because we are applying the same search function either on the left or the right section.

```java
public int searchInsert(int[] nums, int target) {
    // good practice to check null or empty input
    if (nums == null || nums.length == 0) {
        return 0;
    }
    return search(nums, 0, nums.length - 1, target);
}

private int search(int[] nums, int start, int end, int target) {
    // we want to stop when start and end are adjacent to each other
    if (start + 1 >= end) {
        if (target <= nums[start]) {
            return start;
        } else if (target <= nums[end]) {
            return end;
        } else {
            return end + 1;
        }
    }
    // binary search
    int midpoint = (start + end) / 2;
    if (nums[midpoint] == target) {
        return midpoint;
    } else if (nums[midpoint] < target) {
        return search(nums, midpoint + 1, end, target);
    } else {
        return search(nums, start, midpoint - 1, target);
    }
}
```

The stopping condition is doing a bit extra work here. We will see later that this method can be more convenient in other cases. For this question, we have three possible cases\
1\. target < A\[start], return start\
2\. A\[start] < target < A\[end], return end\
3\. A\[end] < target < A\[end+1], return end + 1

## Iterative Implementation

The recursion only keeps track of `start` index and `end` index. We can have two variables outside of the while loop to accomplish the same functionality.

```java
public int searchInsert(int[] array, int target) {
    if (array == null || array.length == 0) {
        return 0;
    }
    int start = 0, end = array.length - 1;
    int mid;
    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (array[mid] < target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    // check the right place to insert
    if (target <= array[start]) {
        return start;
    } else if (target <= array[end]) {
        return end;
    } else {
        return end + 1;
    }
}
```

## Time & Space Complexity

Recursive - O(logn) time (logn) space\
Iterative - O(logn) time O(1) space

The worst case of searching is going down a full path in the tree diagram above. The length of the full path or equivalently the height of the balanced tree is `O(logn)`.

More formally, we can justify the runtime by solving the recurrence `T(n) = T(n/2) + 1`.

```
T(n) = T(n/2) + 1               --> 1
>    = [T(n/4) + 1] + 1         --> 2
>    = [[T(n/8) + 1] + 1] + 1   --> 3
    ...
>    = 1 + 1 + 1 ... + 1 + 1    --> lgn
```

## Follow Up

What if we allow duplicates in the input array?