“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

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 in order.

You must use an O(log n) time complexity algorithm.

Example 1:

Input: nums = [1,3,5,6], target = 5 output: 2Copy the code

Example 2:

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

Example 3:

Input: nums = [1,3,5,6], target = 7 output: 4Copy the code

Example 4:

Input: nums = [1,3,5,6], target = 0 output: 0Copy the code

Example 5:

Input: nums = [1], target = 0 Output: 0Copy the code

Tip:

  • 1 <= nums.length <= 104
  • nums 为Non-repeating elementtheascendingArrangement of array
  • -104 <= target <= 104

Let’s just find the first place that is greater than or equal to the target value.

For this kind of problem, the natural idea is to use binary search to solve the problem

Binary search

Binary lookup applies to finding the first place in an ordered array that matches the condition

The overall method is to compare the middle value of the search interval with the target value each time, judge whether the target value is in the first half or the second half of the current interval through the size relationship, and then adjust the interval to the corresponding part, so that the search interval is halved each time until the element or position that meets the conditions is found

At this point, our problem solution idea is complete, the following is the code implementation

var searchInsert = function(nums, target) {
    if(target<nums[0]) return 0;
    if(target>nums[nums.length-1]) return nums.length;
    let l = 0,r = nums.length-1;
    while(l<r){
        const mid = (l+r)>>1;
        if(nums[mid]<target) l = mid+1
        else r = mid;
    }
    return l;
};
Copy the code

At this point, we are done with Leetcode-35 – searching for the insertion location

If you have any questions or suggestions, please leave a comment!