## 35. Search Insert Position

**Question Type:** Easy

**Liked by :**14.6K

**Disliked by:** 630

## Companies asked this Question:

*Company name : No of Times*

Amazon 4

Google 2

Apple 8

Microsoft 5

Adobe 4

Yahoo 2

Bloomberg 2

Facebook 7

VMware 5

Uber 4

LinkedIn 2

TikTok 2

tcs 2

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 <= 104`

`-104 <= nums[i] <= 104`

`nums`

contains **distinct** values sorted in **ascending** order.

`-104 <= target <= 104`

## Approach:

**Initialize Pointers:**

Initialize two pointers, start and end, to represent the search range within the sorted array.start initially points to the first element (index 0), and end points to the last element (index nums.length - 1).

**Binary Search Loop:**

Enter a while loop that continues as long as start is less than or equal to end.

**Calculate Middle Index:**

Calculate the middle index mid as start + (end - start) / 2. This ensures that the middle index is always rounded down to an integer, avoiding potential overflow issues.

**Compare with Target:**

Check if the element at index mid is equal to the target value.

If they are equal, return mid as the index where the target is found.

**Adjust Pointers:**

If the element at index mid is greater than the target, update end to mid - 1 to search in the left half of the current range.

If the element at index mid is less than the target, update start to mid + 1 to search in the right half of the current range.

**Return Insertion Point:**

If the while loop exits without finding the target (i.e., start becomes greater than end), return start as the index where the target should be inserted.

## Code(in Java):

```
class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end){
int mid = start +(end - start) / 2;
if(nums[mid] == target) return mid;
if(nums[mid] > target) end = mid - 1;
if(nums[mid] < target) start = mid + 1;
}
return start;
}
}
```

**Time Complexity Analysis:**

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This approach ensures that the search is performed efficiently.

Happy coding,

shiva

## Top comments (0)