This is the 16th day of my participation in the First Challenge 2022

Happy New Year to you all

preface

  • Some love each other, some drive at night to watch the sea, someleetcodeYou can’t do the first one, so you can see,leetcodeThe problem has weight. Today we’re going to meet them

Title address

Search for insertion position

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order. You must use an O(log n) time complexity algorithm.

Example 1:

Input: nums = [1,3,5,6], target = 5 output: 2Copy the code

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1Copy the code

Example 3:

Input: nums = [1,3,5,6], target = 7 output: 4Copy the code

Example 4:

Input: nums = [1,3,5,6], target = 0 output: 0Copy the code

Example 5:

Input: nums = [1], target = 0 Output: 0Copy the code

Tip:

1 <= nums.length <= 104-104 <= nums[I] <= 104 NUMs is an ascending array of non-repeating elements -104 <= target <= 104Copy the code

Violence law

Train of thought

  • First we loop through the arraynums
  • Checks whether the current value is greater than or equal totarget
  • If yes, the current value exists in the array, return the corresponding subscript
  • Returns the length of the array if it does not contain values

solution

var searchInsert = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= target) return i
    }
    return nums.length
};
Copy the code

Binary search

Train of thought

Suppose the question asks you to find if there is a target value in a sorted array, then a trained reader should immediately think of using dichotomy to find if there is a target value in order (logn) time. But there’s an extra condition, which is if we need to return the sequential insertion positions when they’re not in the array, can we still use dichotomy? The answer is yes, we just need to tweak it a little bit.

Consider the insertion position pos, which is true if nums[pos−1]

Where NUMs stands for sorted array. Since the target value exists, we return the index pos is equal to or greater than target.

Here, the problem is directly applied to the dichotomy method, that is, constantly use the dichotomy approach to find the first index greater than or equal to target. The following code is the author’s customary dichotomy. The initial value of ANS is set to the length of the array to omit the judgment of the boundary condition, because there is a case where target is greater than all the numbers in the array, and in this case, it needs to be inserted to the length of the array.

solution

var searchInsert = function(nums, target) {
    const n = nums.length;
    let left = 0, right = n - 1, ans = n;
    while (left <= right) {
        let mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
};
Copy the code

Write in the last

  • I hope you find it rewarding