current position:Home>C language algorithm problem: search insertion position

C language algorithm problem: search insertion position

2022-01-27 02:37:42 WE-ubytt

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

Example 4:

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

Example 5:

Input : nums = [1], target = 0
Output : 0

Tips :

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums Arrange the array in ascending order without repeating elements
-104 <= target <= 104

source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/search-insert-position
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas :
according to if Judgment condition ,left The value on the left remains less than target,right The value on the right is always greater than or equal to target, And because the end condition of the loop is left > right, therefore left In the end, it must be equal to right+1, At the end of the cycle , stay left and right Draw a vertical line between , You can just divide the array into two parts :left The left part and right On the right ,left The left part is all smaller than target, And right ending ;right All the parts on the right are greater than or equal to target, And left Led by . So the final answer must be left The location of .

Complexity analysis :

Time complexity :O(\log n)O(logn), among nn Is the length of the array . The time complexity of binary search is O(\log n)O(logn).
Spatial complexity :O(1)O(1). We just need constant space to hold a number of variables .

Code :

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

copyright notice
author[WE-ubytt],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270237409708.html

Random recommended