# Search Insert Position

## Problem

Given a sorted array and a value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

### Example

```
Input : [1,3,5,6] , value = 5
Output: 2
Input : [1,3,5,6] , value = 2
Output: 1
Input : [1,3,5,6] , value = 7
Output: 4
Input : [1,3,5,6] , value = 0
Output: 0
```

## Analysis

An easy method to solve the problem is to iterate through the array comparing target with value if found return, if greater return index since this will be the location of insertion. Time Complexity: `O(n)`

But we can do better! The problem is a search problem, and as we know `BinarySearch`

is better algorithm for searching it will give us Time Complexity = `O(log(n))`

## Solution 1 - Using Recursion

## Solution 2 - Using a loop

Time Complexity : `O(log(n))`

Space Complexity : `O(1)`

*Happy Coding!*

## Leave a Comment