# 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?


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/divide_and_conquer/binary_search/search-insert-position.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.