# Search Insert Position
**Difficulty:** EASY
[External](https://leetcode.com/problems/search-insert-position)
Canonical: https://scaleengineer.com/dsa/problems/search-insert-position
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cognizant](https://scaleengineer.com/companies/cognizant), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Instacart](https://scaleengineer.com/companies/instacart)
---
## Problem
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`

# Approaches
## Linear Scan
This approach involves iterating through the array from the beginning to find the target or its insertion point. It's straightforward but less efficient.
**Time:** O(n) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Works correctly for all cases.
**Cons:** Inefficient for large input arrays.; Does not meet the O(log n) time complexity requirement specified in the problem description.
### Explanation
We can traverse the array `nums` with a single loop. For each element `nums[i]`, we compare it with the `target`. If `nums[i]` is greater than or equal to the `target`, we've found the correct position. This is because the array is sorted, so any subsequent element will also be greater. If we find such an element, we return its index `i`. If the loop finishes without finding any element greater than or equal to the `target`, it implies that the `target` is larger than all elements in the array. In this case, the correct insertion position is at the very end of the array, so we return the length of the array.

```java
class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}
```
### Algorithm
1. Iterate through the array `nums` from index `i = 0` to `n-1`.
2. For each element `nums[i]`, check if it is greater than or equal to the `target`.
3. If `nums[i] >= target`, return the current index `i`.
4. If the loop completes, it means the `target` should be inserted at the end. Return the length of the array.

## Binary Search
This is the optimal approach that leverages the fact that the input array is sorted. By repeatedly dividing the search interval in half, we can find the target or its insertion position in logarithmic time.
**Time:** O(log n) · **Space:** O(1)
**Pros:** Extremely efficient, with logarithmic time complexity.; Meets the problem's performance requirements.; Optimal solution for sorted arrays.
**Cons:** Can be slightly tricky to implement correctly, especially handling the edge cases and the final return value when the target is not found.
### Explanation
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

We initialize two pointers, `low` at the start of the array (index 0) and `high` at the end of the array (index `n-1`). We then enter a loop that continues as long as `low <= high`.

Inside the loop:
1. We calculate the middle index `mid`.
2. If `nums[mid]` is equal to the `target`, we have found the target and return `mid`.
3. If `nums[mid]` is less than the `target`, we know the target must be in the right half of the current search space (if it exists), so we update `low` to `mid + 1`.
4. If `nums[mid]` is greater than the `target`, the target must be in the left half, so we update `high` to `mid - 1`.

If the loop terminates, it means the `target` was not found in the array. The value of the `low` pointer at this point is the index where the `target` would be inserted to maintain the sorted order. This is because the loop invariant maintains that all elements to the left of `low` are smaller than the `target`, and all elements to the right of `high` are larger than the `target`. When `low > high`, `low` points to the first position where an element is greater than or equal to the `target`.

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

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // If the loop finishes, target is not found.
        // 'low' is the insertion point.
        return low;
    }
}
```
### Algorithm
1. Initialize pointers `low = 0` and `high = nums.length - 1`.
2. While `low <= high`, do the following:
   a. Calculate `mid = low + (high - low) / 2`.
   b. If `nums[mid]` equals `target`, return `mid`.
   c. If `nums[mid]` is less than `target`, move the search to the right half by setting `low = mid + 1`.
   d. If `nums[mid]` is greater than `target`, move the search to the left half by setting `high = mid - 1`.
3. If the loop terminates, the `target` is not in the array. The `low` pointer indicates the correct insertion position. Return `low`.

# Solutions
### Java

```java
class Solution {
public
  int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) >>> 1;
      if (nums[mid] >= target) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function ( nums , target ) { let left = 0 ; let right = nums . length ; while ( left < right ) { const mid = ( left + right ) >> 1 ; if ( nums [ mid ] >= target ) { right = mid ; } else { left = mid + 1 ; } } return left ; };
```

### CPP

```cpp
class Solution {
public:
  int searchInsert(vector<int> &nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
      int mid = left + right >> 1;
      if (nums[mid] >= target)
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
};

```

### Python

```python
class Solution : def searchInsert ( self , nums : List [ int ], target : int ) -> int : left , right = 0 , len ( nums ) while left < right : mid = ( left + right ) >> 1 if nums [ mid ] >= target : right = mid else : left = mid + 1 return left
```