**Physical Address**

304 North Cardinal St.

Dorchester Center, MA 02124

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.

You must write an algorithm with `O(log n)`

runtime complexity.

**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
```

**Constraints:**

`1 <= nums.length <= 10`

^{4}`-10`

^{4}<= nums[i] <= 10^{4}`nums`

contains**distinct**values sorted in**ascending**order.`-10`

^{4}<= target <= 10^{4}

```
public int searchInsert(int[] A, int target) {
int low = 0, high = A.length-1;
while(low<=high){
int mid = (low+high)/2;
if(A[mid] == target) return mid;
else if(A[mid] > target) high = mid-1;
else low = mid+1;
}
return low;
}
```

```
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0, high = nums.size()-1;
// Invariant: the desired index is between [low, high+1]
while (low <= high) {
int mid = low + (high-low)/2;
if (nums[mid] < target)
low = mid+1;
else
high = mid-1;
}
// (1) At this point, low > high. That is, low >= high+1
// (2) From the invariant, we know that the index is between [low, high+1], so low <= high+1. Follwing from (1), now we know low == high+1.
// (3) Following from (2), the index is between [low, high+1] = [low, low], which means that low is the desired index
// Therefore, we return low as the answer. You can also return high+1 as the result, since low == high+1
return low;
}
};
```

```
function searchInsert(nums, target) {
return binarySearch(nums, target, 0, nums.length - 1);
};
function binarySearch(array, target, start, end) {
// If the target is less then the very last item then insert it at that item index
// because anything index less then that has already been confirmed to be less then the target.
// Otherwise insert it at that item index + 1
// because any index grater then that has already been confirmed to be greater then the target
if (start > end) return start;
const midPoint = Math.floor((start + end)/2);
// found target
if (array[midPoint] === target) return midPoint;
// search the left side
if (array[midPoint] > target) return binarySearch(array, target, start, midPoint - 1);
// search the right side
if (array[midPoint] < target) return binarySearch(array, target, midPoint + 1, end);
}
```

```
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
return len([x for x in nums if x<target])
```

In our experience, we suggest you solve this Search Insert Position LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Search Insert Position LeetCode Solution

I hope this Search Insert Position LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

**More Coding Solutions >>**