Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

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 the order in which it will be inserted.

You can assume that there are no duplicate elements in the array.

  • The sample

 

Example 1: input:,3,5,6 [1], 5 output: 2 example 2: input:,3,5,6 [1], 2 output: 1 example 3: input:,3,5,6 [1], 7 output: 4 example 4: input:,3,5,6 [1], 0 output: 0Copy the code

 

Ii. Thinking analysis:

  • If the array is smaller than the target value, return the array length, otherwise return an index greater than or equal to the target value
  • There is also a binary search

Three, AC code

/** * @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){ return i; } } return nums.length; }; Status: Elapsed time: 80 ms Memory consumption: 38.7 MBCopy the code

Four,

  • Of course, there is more than one way to do it, and there are many ways to do it, officially using binary search

Ideas and algorithms;

/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function(nums, target) { let n = nums.length; let left = 0, right = n - 1, ans = n; while (left <= right) { let mid = ((right - left) >> 1) + left; if (target <= nums[mid]) { ans = mid; right = mid - 1; } else { left = mid + 1; } } return ans; }; Execution time: 64 ms Memory: 38.6 MBCopy the code
  • In terms of time, binary search is relatively better

For reference only

Refer to the topic

  • Force button (LeetCode)