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

The title

35. Search for insertion locations

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
  • -104 <= nums[i] <= 104
  • nums 为Non-repeating elementtheascendingArrangement of array
  • -104 <= target <= 104

Violent solution

Train of thought

  1. When we get the sorted array, we find out where the elements are inserted.
  2. Run the loop directly from the first element, continue if it is smaller than the element, and return if it is larger than the element.
  3. If you can’t find anything larger than the element, you insert it at the end of the array.

implementation

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var searchInsert = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if(nums[i] >= target) {
            returni; }}return nums.length;
};
Copy the code

Binary search

Train of thought

  1. The average complexity of the above violent solution is O(logn), but if the maximum value is inserted every time, it reaches O(n); It obviously doesn’t meet the requirements of our problem, so we need to optimize it;
  2. We can start at the middle point, and if it’s smaller than the element, we can go from the top half, and if it’s smaller than the element, we can go from the bottom half, and then we only have to do order log2 n searches to find the answer.

implementation

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var searchInsert = function(nums, target) {
    let left = 0, right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
           left = mid + 1; 
        } else {
            right = mid - 1; }}return left;
};
Copy the code

Pay attention to the point

Binary search: mid + 1 for left node and mid – 1 for right node; Otherwise we’ll be stuck in an infinite loop.

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.