Detailed explanation of the example of the search insertion position of Go language problem LeetCode35

Question description

Original topic link:

35. Search for insertion position - LeetCode ()

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 sequentially.

Please use an algorithm with a time complexity of O(log n).

Example 1:

enter: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

enter: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

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

hint:

1 <= <= 10^4

-10^4 <= nums[i] <= 10^4

nums arranges arrays in ascending order with no duplicate elements

-10^4 <= target <= 10^4

Idea Analysis

First, clarify the meaning of the question:

(1) The array is ordered;

(2) If the target value is equal to the target value, return the target value subscript. If it is different, get the subscript in order.

Idea: Use the binary search strategy to obtain the size of the intermediate data and shorten the size and positioning interval of the array, such as the previous section in the middle of the array and the next section in the middle of the array

Get the value of subscript i arrrs[i]>=target, and return the corresponding subscript

AC Code

class Solution {
    public int searchInsert(int[] nums, int target) {
        int index = ( / 2);
        if (nums[index] >= target) {
            return compareByIndex(nums, 0, index+1, target);
        } else
            return compareByIndex(nums, index+1, , target);
    }
    private int compareByIndex(int[] nums, int start, int end, int target) {
        for (int i = start; i < end; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return end;
    }
}

Summarize

This kind of position search method is definitely suitable. Even if the formula of the dichotomy cannot be applied directly, it is also a dichotomy idea and variant.

refer to

❤️ Mind map compilation: summarizes the general template writing method of binary search, completely solving several confusing problems ❤️ - Search for insertion location

Priority to boundary situations Red and blue marking solution

First consider whether the target is >=nums[numsSize-1]. If it is greater than, it will return numsSize, and if it is equal, it will return numsSize-1;

Check the bottom line again, if it is less than or equal to nums[0], it will return nums[0];

else

Define the left boundary left=0 and the right boundary right=numsSize-1;

Enter the loop, narrow the boundary until left+1=right;

If found, it will return directly. If not found at the end of the loop, it will return left+1 (between left and right)

Code

int searchInsert(int* nums, int numsSize, int target){
    if(nums[0]>=target)
    {
        return 0;
    }
    else if(nums[numsSize-1]<target)
    {
         return numsSize;
    }
    else if(nums[numsSize-1]==target)
    {
        return numsSize-1;
    }
    else{
         int r=numsSize-1;
         int i=0;
    while(i+1!=r)
    {
        int mid=(i+r)/2;
    if(nums[mid]>target )
{
    r=mid;
}
        else if(nums[mid]<target)
                 i=mid;
        else{
                 return mid;
 }
    }
            return i+1;

    }
}

The above is the detailed explanation of the detailed explanation of the LeetCode35 search insertion position example. For more information about the Go language search insertion position, please pay attention to my other related articles!