[notes for question brushing] search the insertion position (flexible use of dichotomy)

subject ：

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 to where it will be inserted in sequence .

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

Example 1:

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

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

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

Tips :

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums by   No repeating elements   Of   Ascending   Arrange arrays
-104 <= target <= 104

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/search-insert-position

        First , It is clearly required that the use time complexity is O(log n) The algorithm of , So I choose dichotomy here .（ Because it's in order ）

solution ：

        First, clarify how the dichotomy is filtered in the ordered array ： Find the number in the middle first , Found the subscript that returns the middle . Otherwise, if it is larger than the middle number , Then the interval changes to the right to find , When I was young, I went to the left section to find the middle . Know that the interval is shortened to 0 perhaps 1 until .

        But this problem can't be found only by using the above ordinary dichotomy . Because there is another requirement to return the subscript if it cannot be found .

        therefore , We need an uncertain state . Exclude the array on the premise that it has several numbers , Then this number should be sorted in the subscript of the larger number , It should be smaller than it before .（ If target Larger than all the numbers of the full array should be regarded as a special case ） that , Until the end of the cycle , This endpoint is the subscript we are looking for .

        The above means ：targe If you compare mid Large number , that , At this time [begin, end] There must be no match for its insertion position , conversely , If targe Than mid The number is less than or equal to , that [begin, end] There is a position that matches its insertion , That's right. end. therefore , The code is as follows ：

int searchInsert(int* nums, int numsSize, int target) {
    if (nums[numsSize - 1] < target)
        return numsSize;
    int begin = 0;
    int end = numsSize - 1;
    while (begin < end)
    {
        int middle = begin + (end - begin) / 2;
        if (nums[middle] < target)
        {
            begin = middle + 1;
        }
        else
        {
            end = middle;
        }
    }
    return end;
}