Challenge: Search Insert Position

Problem Statement

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

Input

A sorted array, its size, and a target value

Output

The index at which the array should be inserted OR the index at which it is already present.

Sample Input

  int arr[] = {1,3,5,6};
  int s = 5;
  int arrSize = 4;

Sample Output

2

Coding Exercise

Take a close look and design a step-by-step algorithm before jumping on to implementation. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the hint and solution provided in the code tab. Good Luck!