# Search Insert Position (Leetcode 35) Solution - Top Interview Question Mani
Educating everyone with the beauty of programming!!

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:

```Input: nums = [1,3,5,6], target = 5
Output: 2
```

Example 2:

```Input: nums = [1,3,5,6], target = 2
Output: 1
```

Example 3:

```Input: nums = [1,3,5,6], target = 7
Output: 4
```

Example 4:

```Input: nums = [1,3,5,6], target = 0
Output: 0
```

Example 5:

```Input: nums = , target = 0
Output: 0
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` contains distinct values sorted in ascending order.
• `-104 <= target <= 104`

Solution:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Time Complexity: O(log N) : N is length of input array .
* Space Complexity: O(C) : Constant
* Insert position is nothing but the 'start' index in the iterative search.
* ]0[[[ > start will be left of 0 or right of 0 in case of single element.
*/
class Solution {
public int searchInsert(int[] a, int target) {
int start = 0;
int end = a.length -1 ;

int mid = 0;
while(start <= end) {
System.out.println(start + ":" + end + ":" + mid);
mid = start + (end - start) / 2;
if(target == a[mid]) {
return mid;
}
if(target < a[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
}
``````
Drop your comments below for any questions or comments. For full list of must learn top interview questions Click Here: Must Learn Top Interview Questions

Rating: