Skip to content

Files

Latest commit

 

History

History
277 lines (233 loc) · 8.06 KB

35.search-insert-position.md

File metadata and controls

277 lines (233 loc) · 8.06 KB

35. Search Insert Position

Clarification Questions

  • Is the array empty?
  • Contain duplicates?

Test Cases

Normal Cases

Input: nums = [1,3,5,7], target = 5
Output: 2

Input: nums = [1,3,5,7], target = 6
Output: 1

Edge / Corner 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

Binary Search

To find the target value or the index to insert, then it indicates that we're going to search the smallest number which is equals to or greater than target (it's "floor", "left bound").

[1, 3, 5, 6], target = 5
       ^ // target position

[1, 3, 5, 6], target = 2
    ^ // Insert position, 3 is the smallest number which is equals to or greater than 2.

How about the largest number which is equals to or smaller than target? No, it's not the correct insertion position. From the example [1, 3, 5, 6], target = 2, the correct insertion position is at value 3, not 1.

How can we find the smallest number which is equals to or greater than target? For the normal binary search, we have the following 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], the critial part is here, we should search the left part, because we are not sure if the middle is the smallest number >= target, so we keep searching the left part.

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. For more explanation detail regarding the return value left index, you can check below.

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 critical part, we should search the left part.
    }
    // Why returning left? See below explanation.
    // The possible range is `[0, size]`
    return left
}

// Or equivalently
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
        }
    }
    return left
}

Why Returning left at the End?

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.
..., M, X, ...
        L   target
     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, as same as case 1.
  • 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, and we have already explained the logic 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

Alternative Thinking

Another Important Idea!!

Or you can think in this way, we are looking for the first element that satifies the condition target <= num, our condition is target <= num. and 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:

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

It's similar to First Bad Version.

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, size]:

[O, O, O, O]
 ^ // Not found

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

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

Example

Try the example with only 2 element.

 Position: 0, 1
 Array:   [7, 9]
 3 => [*3, 7, 9]  0 // The result will be 0 if target is smaller than the first element.
 7 => [*7, 7, 9]  0
 8 => [7, *8, 9]  1
 9 => [7, *9, 9]  1
10 => [7, 9, *10] 2 // The result will be `size` if target is larger than the last element.
^                 ^
Target            Insert Position

Bonus

How to find the last element which is <= target (It' "ceiling" or "right bound", not the insert position)?

It's the pattern:

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

We search the last element that satisfies the condition 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
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
}