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

The title

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:

Enter: nums = [1,3,5,6], target = 5

Output: 2

Example 2:

Enter: nums = [1,3,5,6], target = 2

Output: 1.

Example 3:

Enter: nums = [1,3,5,6], target = 7

Output: 4

Example 4:

Enter: nums = [1,3,5,6], target = 0

Output: 0

Example 5:

Enter: nums = [1], target = 0

Output: 0

Tip:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • Nums is an ascending array of non-repeating elements
  • -104 <= target <= 104

Their thinking

Method one: brute force crack

Check whether the value returned by indexOf is equal to -1. If not, return the value of indexOf.

Check whether target is less than nums[0], if yes, return 0;

If target is greater than the maximum value of the array nums[nums.length – 1], nums.length is returned.

Finally, loop through the array NUMs

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

Because the above method is too tedious, after careful consideration, it is found that there is no need to make so many judgments for each layer alone.

You can directly determine the size of target and the current value of the loop, and return the current index if the current value is greater than or equal to target.

Otherwise, no data greater than or equal to the target value is found in the array. Then, the target value is the maximum value and the end of the array is inserted. So return the length of the array.

The optimization is as follows:

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

Of course, the above solution is perfect for this problem. But what they want is an order log n algorithm, which is order n.

Through the algorithm knowledge we have learned, can quickly locate the binary search. 👇

Method two: binary search

/ * * *@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((right - left)/2) + left;
        const mids = nums[mid];
        if (mids < target) {
            left = mid + 1;
        } else {
            right = mid - 1; }}return left;
};
Copy the code

conclusion

This is Xiaokui 🌻, as long as you turn your heart toward the sun, you will have warmth ~

Let’s overcome the algorithm together!!