35. Search insert position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

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 .

You must write an algorithm with O(log n) runtime complexity.

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

Example 1: Example 1:

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

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

Example 2: Example  2:

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

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

Example 3: Example 3:

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

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

Constraints: Tips :

1 <= nums.length <=
- <= nums[i] <=
nums contains distinct values sorted in ascending order.

• nums  by   No repeating elements   Of   Ascending   Arrange arrays

- <= target <=

 

 

 

 

C Language ：

int searchInsert(int* nums, int numsSize, int target){
    int index=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]<target)
        {
            if(i+1==numsSize)
            {
                index=i+1;
                break;
            }
            else if(nums[i+1]>=target)
            {
                index=i+1;
                break;
            }
        }
        else if(nums[i]==target)
        {
            index=i;
            break;
        }
    }
    return index;
}

Execution results ： adopt

Execution time ：4 ms, In all  C  Defeated in submission 94.53% Users of

Memory consumption ：5.7 MB, In all  C  Defeated in submission 97.52% Users of

Pass the test case ：64 / 64

from 《 Two points search 》 On , Learned binary numbers , One bit to the right is divided by 2 Number of numbers , One bit to the left is multiplied by 2 Number of numbers .

C Language ：

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

Execution results ： adopt

Execution time ：4 ms, In all  C  Defeated in submission 94.53% Users of

Memory consumption ：5.8 MB, In all  C  Defeated in submission 69.62% Users of

Pass the test case ：64 / 64