【Day 27 】2021-10-06 - 35. 搜索插入位置

[azl397985856]

35. 搜索插入位置

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/search-insert-position

前置知识

暂无

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

[xy147]

思路

遍历

js代码

var searchInsert = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)

[shixinlovey1314]

Title:35. Search Insert Position

Question Reference LeetCode

Solution

Binary Search, when low > high, low is the postion to insert.

Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() -1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
                return mid;
            else if (target > nums[mid])
                l = mid + 1;
            else 
                r = mid - 1;
        }

        return l;
    }
};

Complexity

Time Complexity and Explanation

O(logn)

Space Complexity and Explanation

O(1)

[yanglr]

思路:

题意：由于题中原数组是从小到大升序排列，故只需找到第一个≥ target的数。

方法: 二分搜索

一开始就提到了题意是由于题中原数组是从小到大升序排列，故需找到第一个≥ target的数。

故二分搜索的目标是：二分出>= target 第一个位置。

check(mid)对应的性质是:

x >= target

假如mid位置的数x满足 x >= target，那么分界点就在mid 的左边，且M 有可能是分界点。

此时右侧区间 [M, R] 是完全满足这个性质的，故可以放心地调整：R = mid,

那么我们可以选择acwing模板1，配套地，L自然需要调整为 mid +1。

// 模板1: 需调整 r = mid
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

代码

实现语言: C++

实现方式1:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if (nums.back() < target) return nums.size();  /* 这种情况需要特判 */
        int L = 0, R = nums.size() - 1;
        while (L < R)
        {
            int mid = (L+R)/2;
            if (nums[mid] >= target)
                R = mid;
            else L = mid + 1;
        }
        return L;
    }
};

注意要进行特殊边界的处理，题意: 1 ≤ nums.length ≤ 10^4， 故不需考虑原数组为空的情况。

但有可能出现原数组最大的数都比 target 小的情况，所以需要一开始就特殊处理这种情况。

实现方式2:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int L = 0, R = nums.size() - 1;
        while (L < R)
        {
            int mid = (L+R)/2;
            if (nums[mid] >= target)
                R = mid;
            else L = mid + 1;
        }
        return (nums[L] >= target) ? L : L + 1;
    }
};

复杂度分析:

• 时间复杂度: O(N logN)
• 空间复杂度: O(1)

[xingzhan0312]

var searchInsert = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

[BpointA]

思路

二分法找位置。边界处理：在右边界放一个正无穷的数，即可判断右边界。所有位置都无法放下的，则说明其小于所有数，放在左边界。

Python3代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left=0
        right=len(nums)-1
        nums.append(float("inf"))

        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]<target and nums[mid+1]>=target:
                return mid+1
            elif nums[mid]<target:
                left=mid+1
            else:
                right=mid-1
        return 0

复杂度

时间复杂度：O(logn)，二分法

空间复杂度：O(1)，两个指针

[kidexp]

thoughts

二分法 把问题等价于找到第一个大于等于这个数

code

class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:
        """
        classic binary search
        """
        if not nums:
            return 0
        start, end = 0, len(nums)-1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid + 1
            elif nums[mid] > target:
                end = mid - 1
            else:
                return mid
        return start

complexity

时间复杂度O(lgn)

空间复杂度O(1)

[mayqiu]

class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1

    while left <= right:
        middle = (left + right) // 2

        if nums[middle] < target:
            left = middle + 1
        elif nums[middle] > target:
            right = middle - 1
        else:
            return middle
    return right + 1

[thinkfurther]

思路

二分查找

代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while(left<=right):
            middle = (left+right)//2
            if nums[middle] == target:
                return middle
            if nums[middle] < target:
                left = middle + 1
            else:
                right = middle - 1

        return left

复杂度

时间复杂度 ：O(log N)

空间复杂度：O(1)

[pophy]

思路

• 2分查找 直接套用模板

Java Code

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right  = mid;
            } else {
                left = mid;
            }               
        }     
        if (target <= nums[left]) {
            return left;
        }       
        if (target <= nums[right]) {
            return right;
        }
        return right + 1;
    }

时间&空间

• 时间 O(log(n))
• 空间 O(1)

[JiangyanLiNEU]

Binary search: runtime=O(nlogn), space = O(1)

JavaScript Code

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length-1;
    let remain = (left+right)%2
    let middle = (left+right-remain)/2

    if (target <= nums[left]){
        return left;
    }else if (target == nums[right]){
        return right;
    }else if (target > nums[right]){
        return right+1;
    }else{
        while (left<right){
            if (nums[middle]==target){
                return middle;
            }else if (nums[middle]>target){
                right = middle;
            }else if (nums[middle]<target){
                left = middle+1;
            };
            remain = (left+right)%2
            middle = (left+right-remain)/2
        };
        return left;
    }

Python Code

class Solution(object):
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums)-1
        if target<= nums[left]:
            return left
        if target>=nums[right]:
            if target == nums[right]:
                return right
            else:
                return right+1
        middle = (left+right)//2
        while left<right:
            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                right = middle
            elif nums[middle] < target:
                left = middle +1 
            middle = (left+right)//2
        return left

[yachtcoder]

bisect_left. O(lgn), O(1).

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l

[zliu1413]

binary search: runtime = O(logN), space = O(1)

class Solution: def searchInsert(self, nums: List[int], target: int) -> int: l,r = 0,len(nums) while l<r: mid = (l+r)//2 if nums[mid] == target: return mid elif nums[mid] < target: l = mid+1 else: r = mid return r

[ZacheryCao]

Soliution

Binary search. Two pointers: left, right. We will use mid = left + (right - left) // 2 to decide update left or right. When nums[mid] < target, which means target is on the right side of the mid, we update left = mid + 1. Else right = mid. If nums[mid] == target, return mid. The loop will be terminated when left == right

Code (python)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        if target > nums[-1]:
            return len(nums)
        if target < nums[0]:
            return 0
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

Complexity:

Time: O(log n) Space: O(1)

[mmboxmm]

思路

二分模版千千万

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;

        int start = 0, end = nums.length - 1;

        while (start <= end) {
            int mid = (start + end) >>> 1;
            if (nums[mid] == target) return mid;
            if (nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}

[florenzliu]

Explanation

• since the list is sorted, use binary search
• at each round, find the mid point
  • if the mid point is equal to target, return the index of the mid point
  • if the mid point is larger than target, search the remaining left side of the mid point
  • if the mid point is smaller than target, search the remaining right side of the mid point
• stop when the start point is larger than the end point, and return start point as the insertion position

Python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def bsearch(start, end, target):
            if start > end:
                return start
            mid = (start + end) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                return bsearch(start, mid-1, target)
            else:
                return bsearch(mid+1, end, target)
        return bsearch(0, len(nums)-1, target)

Complexity:

• Time Complexity: O(logN)
• Space Complexity: O(1)

[ZiyangZ]

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return left;
    }
}

[falconruo]

思路:

方法一、 双指针法, 一个指针l指向当前不重复项，另一个指针i循环向右:

1. 遍历整个数组比较nums[l]与nums[i]的值
   • 相等则i继续右移一位
   • 不等则将l右移一位，并将nums[l]的值 = nums[i]
2. 最后返回l + 1

方法二、二分查找(Binary Search) 每次取中间位置m与目标数字比较：

• 如果nums[m] == target直接返回
• 通过nums[m] > target，则取左半子数组继续查找
• 通过nums[m] < target，则取右半子数组继续查找

复杂度分析: 方法一、 时间复杂度: O(n), n为数组nums元素个数 空间复杂度: O(1)

方法二、 时间复杂度: O(logn), n为数组nums元素个数 空间复杂度: O(1)

代码(C++):

方法一、遍历
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0;

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < target)
                ++l;
            else
                break;
        }

        return l;
    }
};

方法二、二分查找
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();

        while (l < r) {
            int m = l + (r - l)/2;
            if (nums[m] == target) return m;

            if (nums[m] > target) r = m;
            else
                l = m + 1;
        }

        return l;
    }
};

[Menglin-l]

思路：

二分法

找到位置就返回位置索引，找不到就返回left索引。

---

代码部分：

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) return -1;

        int left = 0; 
        int right = nums.length - 1;

        while (left <= right) {

            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else if (target == nums[mid]){
                return mid;
            }
        }

        return left;
    }
}

---

复杂度：

Time: O(logN)

Space: O(1)

[zhangzz2015]

思路

• 当在一个有序或者部分有序进行查找，可考虑使用二分查找。二分查找关键点，区间的定义，退出的条件。使用左闭右闭，因此while 退出条件为 left > right 当找到target 则返回。小于target 则在右半部分搜索，否则在左半边搜索。当数组没有target。最后的退出情况下 [right left] 因此 left> target 的index right< target index。返回left。时间复杂度为O(logN)。空间复杂度为O(1)

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {

        int left =0; 
        int right = nums.size()-1; 

        while(left<=right)
        {
            int middle = left + (right -left)/2; 
            if(nums[middle]==target)
            {
                return middle; 
            }
            else if(nums[middle]<target)
            {
                left = middle+1;
            }
            else
            {
                right = middle-1; 
            }
        }

        return left; 

    }
};

[heyqz]

code

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1

        while l <= r:
            m = (r + l) // 2
            if nums[m] == target:
                return m
            elif target > nums[m]:
                l = m + 1
            elif target < nums[m]:
                r = m - 1
        return l

complexity

time: O(logn) space: O(1)

[joeytor]

思路

l, r 分别是 0, len(nums)-1, 在闭区间 [0, len(nums)-1] 中查找

循环条件是 l≤r 因为是在闭区间中查找, 所以 [i,i] 也是一个 valid interval

最后跳出循环时的条件时满足 l=r+1, 所以 返回 l 是新的 insert index

代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid
        return l

复杂度

时间复杂度: O(logn)

空间复杂度: O(1)

[zol013]

思路： 二分查找

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if target == nums[mid]:
                return mid
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
        return l

Time Complexity: O(log(n)) Space Complexity: O(1)

[leo173701]

class Solution: def searchInsert(self, nums: List[int], target: int) -> int:

    if target<nums[0]:
        return 0
    elif target > nums[-1]:
        return len(nums)
    else:
        start = 0
        end = len(nums)-1
        while(start<=end):
            mid = start+int((end-start)/2)
            if nums[mid]==target:
                return mid
            elif nums[mid]<target:
                if nums[mid+1]>target:
                    return mid+1
                start = mid+1
            else:
                end = mid -1

[ninghuang456]

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;
        int left = 0; int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left)/ 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            } 
        }
        return left; 
    }
}
Time O(logn)
Space O(1)

[bolunzhang2021]

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i=0;
       for(; i<nums.length;i++)
       {
           if(nums[i]<target)
           continue;
           if(nums[i]==target)
           return i;
           if(nums[i]>target)
           return i;
       }
       return i;
    }
}

Time O(logn) Space O(1)

[Yufanzh]

Intuition

Problem ask for O(logN) time complexity, then binary search is the way. pay attention to whether it is [left, right] or [left, right)

Algorithm in python3

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return left

Complexity Analysis:

• Time complexity: O(logn)
• Space complexity: O(1)

[chakochako]

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left , right = 0, len(nums)

        while left < right:

            mid = left + (right - left)//2
            if target == nums[mid]:
                return mid
            if target > nums[mid]:
                left = mid + 1
            elif target < nums[mid]:
                right = mid
        return left

[wangzehan123]

public class Solution {
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int start = 0;
        int end = A.length - 1;
        int mid;

        if (target < A[0]) {
            return 0;
        }
        // find the last number less than target
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (A[end] == target) {
            return end;
        }
        if (A[end] < target) {
            return end + 1;
        }
        if (A[start] == target) {
            return start;
        }
        return start + 1;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[xj-yan]

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left + 1 < right){
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid;
            else left = mid;   
        }
        if (nums[right] < target) return right + 1;
        else if (nums[left] < target) return right;
        else return left;
    }
}

Time Complexity: O(logN), Space Complexity: O(1)

[leungogogo]

LC35. Search Insert Position

Method. Binary Search

Main Idea

Find the first element that is greater than target, and that's the insert position.

Since the array is sorted, we can apply binary search.

Code

• cpp

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        // Find the first element that is larger than target.
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l] >= target ? l : l + 1;
    }
};

Complexity Analysis

Time: O(logn)

Space: O(1)

[ginnydyy]

Problem

https://leetcode.com/problems/search-insert-position/

Notes

• Binary search
• Pay attention to template and edge cases:
  • start from 0, end from nums.length - 1
  • while(start + 1 < end)
  • mid = start + (end - start)/2, to avoid overflow
  • check <, >, == cases in the loop
  • after the loop check <=left, >right, >left && <=right cases

Solution

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left + 1 < right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                return mid;
            }
        }
        if(target <= nums[left]){
            return left;
        }
        if(target > nums[right]){
            return right + 1;
        }
        return right;

    }
}

Complexity

• Time: O(logn), binary search (n is the length of nums).
• Space: O(1).

[pan-qin]

idea: binary search code:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int low=0, high=nums.length-1;    
        while(low<=high) {
            int mid=(low+high)/2;
            if(nums[mid]== target)
                return mid;
            else if(nums[mid]>target)
                high=mid-1;
            else
                low=mid+1;
        }
        return low;
    }
}

Time: O(logn) Space: O(1)

[AgathaWang]

暴力法一遍循环

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 指针
        # O(N)
        if target in nums:
            return nums.index(target)
        for i in range(len(nums)):
            if nums[i] > target:
                return i
        return len(nums)

[xieyj17]

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target > nums[-1]:
            return len(nums)
        if target < nums[0]:
            return 0

        if len(nums) == 1:
            if target > nums[0]:
                return 1
            else:
                return 0

        left = 0
        right = len(nums)-1
        while left <= right:
            mid = int(left + (right-left)/2)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid-1
            else:
                left = mid + 1
        return left

使用二分法

Space: O(1)

Time: O(logN)

[SunnyYuJF]

思路

Binary Search

代码 Python

def searchInsert(self, nums: List[int], target: int) -> int:
        l=0
        r=len(nums)-1
        while l<=r:
            mid =(l+r)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]<target:
                l=mid+1
            else:
                r=mid-1
        return l

复杂度分析

时间复杂度： O(logN)
空间复杂度： O(1)

[chen445]

思路

Binary Search

代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left,right=0,len(nums)
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid
        return left

复杂度

Time: O(logn)

Space: O(1)

[hwpanda]

var searchInsert = function(nums, target) {
  let result = 0;
  nums.forEach((x,i) => {

  if (x === target) {
      return i;
   } else if (x < target) {
       result = i + 1
   }

  })
  return result;

};

[nonevsnull]

思路

• 拿到题的直觉解法
  • O(logN)和sorted，都指向二分

AC

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while(left <= right){
            int mid = left + (right - left) / 2;

            if(nums[mid] > target){
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        return left;
    }
}

复杂度

time: O(logN) space: O(1)

[zjsuper]

idea: fast and slow pointers log(N)

Class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        while left<right:
 #           if (left+right) % 2 ==0:
#                mid = (left+right)//2 -1
#            else:
            mid = (left+right)//2

            if nums[mid] == target:
                return mid

            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] >target:
                right = mid-1
        if nums[left] == target:
            return left
        elif nums[left] < target:
            return left+1
        else:
            return left

[guohuijiedesu]

思路

二分查找

代码

''' class Solution: def searchInsert(self, nums: List[int], target: int) -> int:

return bisect.bisect_left(nums, target)

    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target:
            return m
        if nums[m] < target:
            l = m + 1
        else:
            r = m - 1
    return l

'''

[ai2095]

LC35. Search Insert Position

https://leetcode.com/problems/search-insert-position/

Topics

• Array
• Two Pointers

Similar Questions

Easy

Medium

思路

Binary search

代码 Python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1

        return left

复杂度分析

时间复杂度： O(LogN)
空间复杂度：O(1)

[RocJeMaintiendrai]

题目

https://leetcode-cn.com/problems/search-insert-position/

思路

二分法即可

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] > target) {
                right = mid - 1;
            }  else {
                left = mid + 1;
            }
        }
        return left;
    }
}

复杂度分析

时间复杂度

O(logn)

空间复杂度

O(1)

[laofuWF]

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid_index = left + (right - left) // 2
            if nums[mid_index] == target:
                return mid_index

            if nums[mid_index] < target:
                left = mid_index + 1
            else:
                right = mid_index - 1

        return left

[mannnn6]

思路

二分

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

复杂度

时间复杂度： O(LogN) 空间复杂度：O(1)

[Moin-Jer]

思路

---

有序数组使用二分查找

代码

---

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

复杂度分析

---

• 时间复杂度： O(logn)
• 空间复杂度： O(1)

[septasset]

思考

关键点

代码(Python)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while l<r:
            mi =  (l+r) // 2
            if nums[mi] == target: return mi
            if nums[mi]<target:
                l = mi+1
            else:                
                r = mi
        return r

复杂度分析

• 时间：O(logn)
• 空间：O(1)

[flame0409]

思路：二分查找到应该存在的位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i <= j){
            if(nums[(i + j)/2] > target){
                j = (i + j)/2 -1;
            }else if(nums[(i + j)/2] < target){
                i = (i + j)/2 + 1;
            }else {
                return (i + j)/2;
                }
        }
        return i;

    }
}

时间复杂度：O（logn）

空间复杂度：O（1）

[Cartie-ZhouMo]

思路

二分法，寻找大于等于target的数的下界。

代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while l < r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        return r

复杂度

• 时间：O(logN)
• 空间：O(1)

[yingliucreates]

link:

https://leetcode.com/problems/search-insert-position/

代码 Javascript

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

    return target > nums[left] ? left + 1 : left;
};

复杂度分析

time O(lgn) space O(1)

[kennyxcao]

35. Search Insert Position

Intuition

• Binary Search
  • Find first equal or larger

Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const searchInsert = function(nums, target) {
  let start = 0;
  let end = nums.length;
  while (start < end) {
    const mid = start + ~~((end - start) / 2);
    if (nums[mid] >= target) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return start;
};

Complexity Analysis

• Time: O(log(n))
• Space: O(1)
• n = len(nums)