# LeetCode 35. Search Insert Position

## Description

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`

## Explanation

To do a search in a sorted array, we can consider using binary search to achieve. Just by following basic binary search principle, to compare mid position value with target value constantly and we can find the target or the right place to insert the target.

## Java Solution

``````class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;

while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}

if (nums[end] < target) {
return end + 1;
} else if (nums[start] >= target) {
return start;
} else {
return end;
}
}
}``````

## Python Solution

``````class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:

start = 0
end = len(nums) - 1

while start + 1 < end:
mid = start + (end - start) // 2

if nums[mid] == target:
end = mid
elif nums[mid] < target:
start = mid
else:
end = mid

if nums[start] >= target:
return start

if nums[end] >= target:
return end

return end + 1``````
• Time Complexity: O(log(N))
• Space Complexity: O(1)

## 4 Thoughts to “LeetCode 35. Search Insert Position”

1. Parth says:

Please do a video on 38. Count and Say leetcode problem too. I am unable to understand that.

Thanks

2. Ade says:

Hi GoodTecher,
You are doing a nice work on helping me to improve my problem-solving skill.
Here is one LeetCode that I need you to explain – LeetCode 278 First Bad Version.
Regards

1. GoodTecher says:

Thank you Ade. Will take a look at the question 🙂