Skip to content

35.search-insert-position.md

Latest commit

 

History

History
271 lines (224 loc) · 8.07 KB

35.search-insert-position.md

File metadata and controls

271 lines (224 loc) · 8.07 KB

35. Search Insert Position

Key Insights

  • If the target exists in the array, we return the index of the target, it's the same as the normal binary search.
[1, 3, 5, 6], target = 5
       ^ // target position
  • If the target does not exist in the array, we return the index to insert the target. Where can we insert so that the array is still sorted?
[1, 3, 5, 6], target = 2

// Before 1
[2, 1, 3, 5, 6] // Not sorted

// Before 3 (After 1)
[1, 2, 3, 5, 6] // Sorted, correct insert position!!

// After 3
[1, 3, 2, 5, 6] // Not sorted

We must insert before 3, because 3 is the smallest number ≥ 2.

❌ Wrong idea: finding the largest number ≤ target will not give the correct insert position. From the example [1, 3, 5, 6], target = 2, the correct insertion position is at value 3, not 1.

Binary Search

From above insight, we know that to find the target value or the index to insert, we must search the smallest number ≥ target.

How can we find the smallest number which is equals to or greater than target? For the normal binary search, we have the 3 conditions:

  • If target < nums[middle], we should search the left part. (The normal binary search condition)
  • If nums[middle] < target, we should search the right part. (The normal binary search condition)
  • If target == nums[middle], we just return middle immediately.

The key difference between the normal binary search and the search insert position is that we return left at the end. (See below explanation)

fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    
    while (left <= right) {
        val middle = left + (right - left) / 2

        // As same as normal binary search.
        if (nums[middle] == target) return middle
        else if (nums[middle] < target) {
            left = middle + 1
        } else if (target < nums[middle]) {
            right = middle - 1
        }
    }
    // Insert position
    return left
}

Why Return left?

As we have while (left <= right), in the last iteration we have the following cases:

Case 1. left == middle == right

When size is odd, or simply size is 1:

[..., X, ...]
      L
      M
      R
  • If target <= nums[middle], then middle should be the correct answer and we should search left part by moving right = middle - 1. At the moment, the while loop terminates, left is at the same position of middle, so it is the correct answer.
......., X, M, ...
target      L
         R
  • If nums[middle] < target, middle + 1 should be the correct answer, and we should search right part by moving left = middle + 1. At the moment, the while loop terminates, left is the correct answer.
        * target
..., M, X, ...
        L   
     R

Case 2. left == middle = right - 1

When size is even, or simply size is 2:

[..., X, X, ...]
      L  R
      M
  • If target <= nums[middle]: middle is the correct answer, we search the left part by moving right = middle - 1, then it becomes the case left == middle == right, and we have already explained the logic above.
  • If nums[middle] < target: We should search right part, we move left = middle + 1 which is equal to right, then it becomes the case left == middle == right, same as above.

Source: https://leetcode.com/problems/search-insert-position/solutions/15080/my-8-line-java-solution/comments/524126

https://leetcode.cn/problems/search-insert-position/solutions/8017/hua-jie-suan-fa-35-sou-suo-cha-ru-wei-zhi-by-guanp/comments/1079722

Binary Search (Variant 1)

We can use the same key idea of 34. Find First and Last Position of Element in Sorted Array, the key part is that if we find the target, we should keep searching the left part, because we are not sure if the middle is the smallest number >= target.

This approach is also applicable to the array with duplicates.

The left pointer is the index of the smallest number >= target, and the right pointer is the index of the largest number <= target after the while loop breaks.

fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (target < nums[middle]) right = middle - 1       // Normal binary search condition
        else if (nums[middle] < target) left = middle + 1   // Normal binary search condition
        else if (target == nums[middle]) right = middle - 1 // The key part, we should search the left part.
    }
    return left
}

Binary Search (Variant 2)

Or we can use the same idea of First Bad Version, we are looking for the first element that satifies the condition target <= num.

For example, we have the following array, X indicates the numbers that doesn't meet the condition (the numbers < target), and O indicate the number met the condition (the numbers >= target), then the smallest number which is equals to or greater than target is the first O we want:

target = 4
 1, 2, 3, 5, 6, 7, 8
[X, X, X, O, O, O, O]
          ^ // target
 L                 R
fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        // Looking for the first element that satifies the condition.
        if (meetCondition(target, nums[middle])) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

// Condition: target <= num
private fun meetCondition(target: Int, num: Int): Boolean {
    return target <= num
}

Possible left Range

The left pointer is in the range [0, n]:

[O, O, O, O]
 ^ // target found

[X, X, O, O]
       ^ // target found

[X, X, X, X], n
              ^ // target not found

Edge Cases

  • The target is smaller than the first element.
Input: nums = [1,3,5,7], target = 0
Output: 0
  • The target is larger than the last element.
Input: nums = [1,3,5,7], target = 8
Output: 5

Bonus: Last Element <= Target

How to find the last element which is <= target? It's the pattern:

[O, O, O, X, X, X, X]
       ^ // target

We search the last element that satisfies the condition num <= target.

fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    
    while (left <= right) {
        val middle = left + (right - left) / 2

        if (target < nums[middle]) {
            right = middle - 1
        } else if (target == nums[middle]) { // We are not sure if it's the last element, so we keep searching the right part.
            left = middle + 1
        } else if (nums[middle] < target) {
            left = middle + 1
        }
    }
    return right
}

// Or equivalently, we search the last element that satisfies the condition `num <= target`.
fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    
    while (left <= right) {
        val middle = left + (right - left) / 2

        // Looking for the last element that satisfies the condition.
        if (meetCondition(target, nums[middle])) {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    // The possible range is `[-1, size - 1]`
    return right
}

// Condition: num <= target
private fun meetCondition(target: Int, num: Int): Boolean {
    return num <= target
}

Possible right Range

The right pointer is in the range [-1, size - 1]:

// Possible range, determinicis
_, [X, X, X, X]
^ // Not found

[X, X, O, O]
          ^ // target

[O, O, O, O]
          ^ // target

Example

[1, 3, 7] target = 5
 O  O  X
    ^

[1, 3, 3, 3] target = 3
 O  O  O  O
          ^

-1 [7, 7, 7] target = 5 // return -1
    X  X  X
 ^
    L
    M
 R

[1, 1, 1] target = 5
 O  O  O
       ^
          L
       M
       R