This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

Search for insertion position (Question number 35)

The title

Given a sort 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 order in which it will be inserted.

You must use order log n algorithms.

Example 1:

Input: nums = [1.3.5.6], target = 5Output:2
Copy the code

Example 2:

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

Example 3:

Input: nums = [1.3.5.6], target = 7Output:4
Copy the code

Example 4:

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

Example 5:

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

Tip:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • numsAn ascending array with no repeating elements
  • -104 <= target <= 104

link

Leetcode-cn.com/problems/se…

explain

This problem, this problem is Jane I hit (simple problem I punch).

If you don’t look at the mandatory requirement:

You must use order log n algorithms.

So the actual operation would be very simple, just go through it once, and if we’re lucky we don’t even have to go through it, but the time to do that would be order n, which is not the norm, but this order nlogn is telling us to do it in two.

I’m just going to update the left and right positions based on mid until left is greater than right, so the condition for the while loop is left <= right.

Now, let’s look at the basic principles of dichotomy. First of all, it’s an ascending array with no duplicates.

So mid is half of the sum of the left pointer and the right pointer, and then divide by integers using the floor, notice that this is not rounding, it is simply taking the integer part, not the decimal part. There’s a reason we don’t have a decimal part here, because when we do this, we’re going to add +1 or -1 to the mid, and if we round it off, we’re going to add two digits, and that’s not a good idea.

If I get mid, if mid is larger than the target, then I prove that the target is in the first half of the array, so I’ll just set right to mid-1; If mid is smaller than the target, then prove that the target is in the second half of the array, in which case, set left to mid+1. Why is it plus 1? Because mid has been excluded, there is no point in inserting mid into the existence interval, and more importantly, because the terminating condition of the loop is left <= right. If mid is not operated +1 or -1, left will never be larger than right, and then the loop will never end, and an infinite loop is created.

Back to the question itself, why is the last left value the target position? There are two cases:

  • Target exists in an array

    The loop is going to go all the way to the right+1 part, where right is assigned mid-1, and it’s going to get smaller and smaller until right < left, in which case left is going to be the answer

  • Target does not exist in the array

    If the left pointer is smaller than target, and the right pointer is larger than target, then the left pointer is where target should be inserted

Having said that, let’s go straight to the code

Your own answer (double pointer)

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

Same idea, loop until the end of the condition, nothing to say.

Official answer (double pointer)

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

The official answer seems to be a bit superfluous. The ans variable has to be saved, which may be an optimization at the level of code understanding, but we don’t know here.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)