Leetcode 35. Search Insert Position

Problem

Given a sorted array and a target value, we are supposed to find the index of the target in the array. If the target is not in the array, our goal is to find the position where it should be inserted such that the order of the array is maintained. We can assume that there are no duplicate values in the array.

Let's walk through an example to get a real understanding. Given the array [1,3,5,6] and the target 5. The index of 5 in the array is 2, so our function should return 2.

But what if our target is 2? It's not in the array. So we should return the index at which 2 would be inserted while maintaining the order of array. The number 2 should be placed between 1 and 3, at index 1. So our function should return 1.

Approach

The approach used in the solution is Binary Search. Binary Search is a divide and conquer algorithm used in sorted lists. It works by repeatedly dividing the list in half. If the target is at the midpoint, the function returns the midpoint. If it isn't, the half in which the target cannot lie is eliminated and the search continues on the remaining half.

It's better visualised like this:

1
2
3  array: [1,3,5,6]
4  target: 2
5  
6  l points to the first index: l = 0
7  r points to the the size of array: r = 4
8  
9  while l is less than r:
10    calculate the midpoint: m = 2
11    if target is equal to the element at the midpoint:
12      return m
13    if target is greater than the element at the midpoint:
14      move the pointer l to m + 1
15    else 
16      move the pointer r to m

At the end of our while loop, if the target is not present in the array. We will be left with the index (l) where it should be inserted.

Solution

Python Solution

1
2python
3class Solution:
4  def searchInsert(self, nums: List[int], target: int) -> int:
5    l = 0
6    r = len(nums)
7
8    while l < r:
9      m = (l + r) // 2
10      if nums[m] == target:
11        return m
12      if nums[m] < target:
13        l = m + 1
14      else:
15        r = m
16
17    return l

Java Solution

1
2java
3class Solution {
4  public int searchInsert(int[] nums, int target) {
5    int l = 0;
6    int r = nums.length;
7
8    while (l < r) {
9      int m = (l + r) / 2;
10      if (nums[m] == target)
11        return m;
12      if (nums[m] < target)
13        l = m + 1;
14      else
15        r = m;
16    }
17
18    return l;
19  }
20}

JavaScript Solution

1
2javascript
3class Solution {
4  searchInsert(nums, target) {
5    let l = 0;
6    let r = nums.length;
7
8    while (l < r) {
9      const m = Math.floor((l + r) / 2);
10      if (nums[m] === target)
11        return m;
12      if (nums[m] < target)
13        l = m + 1;
14      else
15        r = m;
16    }
17
18    return l;
19  }
20}

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int searchInsert(vector<int>& nums, int target) {
6    int l = 0;
7    int r = nums.size();
8
9    while (l < r) {
10      const int m = (l + r) / 2;
11      if (nums[m] == target)
12        return m;
13      if (nums[m] < target)
14        l = m + 1;
15      else
16        r = m;
17    }
18
19    return l;
20  }
21};

C# Solution

1
2csharp
3public class Solution {
4  public int SearchInsert(int[] nums, int target) {
5    int l = 0;
6    int r = nums.Length;
7
8    while (l < r) {
9      int m = (l + r) / 2;
10      if (nums[m] == target)
11        return m;
12      if (nums[m] < target)
13        l = m + 1;
14      else
15        r = m;
16    }
17
18    return l;
19  }
20}

As evident in the solutions, the binary search algorithm is implemented by maintaining two pointers (l and r) at the ends of the array. The middle point is calculated and used to eliminate half of the search space at each iteration of the while loop. At the end, if the target is not found in the array, the left pointer denotes the index where the target should be inserted.# Time Complexity

The time complexity of the solutions is O(log(n)), because with each iteration we are halving the search space. This represents logarithmic time complexity, a significant improvement over linear search which would take O(n) time where n is the length of the input array.

Space Complexity

The space complexity of the solutions is O(1), as we are not using any extra space that scales with the size of the input array.

Conclusion

Binary Search is a powerful algorithm that can be used to solve a wide range of problems involving sorted arrays or lists. It's quite efficient as it reduces the search space by half in each step, leading to a time complexity of O(log(n)). And with space complexity of O(1), it's very space-efficient as well.

It's also worth noting that although we've demonstrated how to use Binary Search algorithm to solve this specific problem of finding the correct position of a target in a sorted array, it can be used to solve other, more complex problems as well. You may encounter such problems in competitive programming contests or coding interviews, so having a good understanding of Binary Search and how to implement it is crucial.

The key take-away from this article is the ability to understand and implement binary search in any programming language. As seen in the solutions above, the same binary search strategy was implemented in Python, JavaScript, Java, C++ and C#, demonstrating its broad applicability and relevance across different programming languages.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫