35. Search the insertion position

35. Search insert location

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
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer key

Where to find the target value in an ordered array , Use dichotomy

function searchInsert(nums: number[], target: number): number {
    
    let left = 0;
    let right = nums.length-1;
    let mid:number;
    while(left<=right){
    
        mid = (left+right) >> 1;
        if(nums[mid]==target)return mid;
        else if(nums[mid]<target) left = mid+1; // It shows that the result is in the right half interval 
        else right = mid-1;// It shows that the result is in the left half interval 
    }
    // It means that we didn't find 
    return left;
};

This problem can also be solved violently

function searchInsert(nums: number[], target: number): number {
    
    for(let i=0;i<nums.length;++i){
    
        // If it is smaller than the target, continue to look down , The position of the first value larger or equal to the target is the position of the inserted value 
        if(nums[i]>=target)return i ;
    }
    return nums.length;
};