preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

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 must use order log n algorithms.

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

Example 4: input: nums = [1,3,5,6], target = 0 output: 0

Example 5: Input: nums = [1], target = 0 Output: 0

Link: leetcode-cn.com/problems/se…

Answer key

  1. The problem requires O(logn) time complexity, combined with the sorted array in the problem, these two characteristics indicate that the method of binary search should be used to solve the problem, combined with the role of g function in the template, that is, the condition is satisfied. Order logn time.
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var searchInsert = function (nums, target) {
  let l = 0;
  let r = nums.length;
  while (l < r) {
    let m = l + Math.floor((r - l) / 2);
    if (nums[m] >= target) {
      r = m;
    } else {
      l = m + 1; }}return l;
};
Copy the code