# 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 2 - Using a loop

Time Complexity : O(log(n)) Space Complexity : O(1)

Happy Coding!

Tags:

Updated: