search

leetcode-pp / 91alg-6-daily-check

91 算法第六期打卡仓库
28 stars 0 forks source link

【Day 27 】2022-01-07 - 35. 搜索插入位置 #35

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

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
yan0327 commented 2 years ago

思路： 一个最左二分查找即可

func searchInsert(nums []int, target int) int {
    l,r := 0,len(nums)
    for l < r{
        mid := l + (r-l)>>1
        if target > nums[mid]{
            l = mid+1
        }else{
            r = mid
        }
    }
    return l
}

时间复杂度O（NlogN） 空间复杂度O（1）

Alfie100 commented 2 years ago

LeetCode题目连接： 35. 搜索插入位置https://leetcode-cn.com/problems/search-insert-position/

解题思路

二分查找

Python 代码

1. 不失一般性的二分查找：

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

2. 考虑到数组中不存在重复元素，可找到target后直接返回：

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:
                return mid
            elif nums[mid] < target:
                left = mid+1
            else:
                right = mid

        return left

复杂度分析

CodeFarmersWorld commented 2 years ago

func searchInsert(nums []int, target int) int { l,r := 0,len(nums) for l < r{ mid := l + (r-l)>>1 if target > nums[mid]{ l = mid+1 }else{ r = mid } } return l }

BpointA commented 2 years ago

思路

二分法

JAVA代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int 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;

    }
}
tian-pengfei commented 2 years ago 
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int pos = 0;
        for(int num:nums){
            if(nums[pos] >=target){
                return pos;
            }
            pos++;
        }
        return pos;
    }
};
yetfan commented 2 years ago

思路 二分 left左边的值一直保持小于target，right右边的值一直保持大于等于target，最终l = r

代码

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

复杂度 时间 O(log n) 空间 O(1)

charlestang commented 2 years ago

思路

标准二分查找，Python 可以用库函数 bisect.bisect_left(nums, target)。

时间复杂度 O(logn)。

代码

class Solution:
    #def searchInsert(self, nums: List[int], target: int) -> int:
    #    return bisect.bisect_left(nums, target)
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n - 1

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

思路

二分查找插入位置，可以套模板。

代码

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

复杂度分析

hulichao commented 2 years ago

思路

从左到右第一个大于等于 target的位置 左闭右闭写法 case 目标值在0位置，目标值在length位置，目标值在target的位置，目标值在x< target < y

代码

class Solution {
    // 从左到右第一个大于等于 target的位置
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

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

        }

        return r + 1;
    }
}

复杂度分析

LannyX commented 2 years ago

思路

2分查找

代码

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

复杂度分析

cszys888 commented 2 years ago 
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        start, end = 0, n - 1
        while start <= end:
            mid = (start + end)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid - 1
            else:
                start = mid + 1
        return start

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

xianxianxianyu commented 2 years ago

复习周的倔强.jpg

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i = 0;i < nums.size();i++){
            if(nums[i] == target){
                return i;
            }
        }
        for(int i = 0;i < nums.size();i++){
            if(nums[i] > target){
                return i;
            }
        }
        return nums.size();
    }
};
LinnSky commented 2 years ago

思路

暴力解放

代码

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

复杂度分析

思路

Binary Search reduce the time complexity to O(logN)

代码

      var searchInsert = function(nums, target) {
         const n = nums.length
         let left = 0, right = n - 1, res = n;
         while(left <= right){
             let mid = ((right - left) >> 1) + left
             if(target <= nums[mid]){
                res = mid
                right = mid - 1
             } else {
                left = mid + 1
             }
         }
         return res
      };
arteecold commented 2 years ago

二分

left左边的值一直保持小于target，right右边的值一直保持大于等于target，最终l = r

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

O(log n)

zhiyuanpeng commented 2 years ago 
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]:
                r = mid - 1
            if target > nums[mid]:
                l = mid + 1
            if target == nums[mid]:
                return mid
            if l==r:
                if nums[l] < target:
                    return l + 1
                if nums[l] > target:
                    return l
        return l
zjsuper commented 2 years ago 
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 target < nums[mid]:
                r = mid-1
            elif target > nums[mid]:
                l = mid+1

        print(l,r)
        if l == r:
            if target == nums[l]:
                return l
            elif target < nums[l]:
                return l
            else:
                return l+1
        elif l>r:
            return l
        else:
            return r
qihang-dai commented 2 years ago

二分查找：基本功很重要。

二分要两种写法：while(left <= right)和while(left < right)。

mid 总是 l + (r - l)/2的，有些奇怪的不规范写反会变成l +(r - l + 1)/2，是为了防止进入死循环，这个尽量不要用，把区间的开闭搞的乱七八糟

<= 表示区间left = right 有意义， 左闭右闭，那么如果mid不满足tar, 则l = mid + 1, r = m -1如此 < 表示是左闭右开， 则l = mid + 1， r = mid(开所以取Mid无所谓）。 如果是左开右闭（]， 则 r = mid - 1, l = mid; m = l + ( r- l + 1)/2 了，但是很少见 用的惯的模板才是最适合你的，切记


class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.length;

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

        return r;
    }
}
AlduinLeung commented 2 years ago 
var searchInsert = function(nums, target) {
    //标准二分法解题
    let left = 0
    let right = nums.length-1;
    while(left <=right){
        let mid = parseInt((left+right)/2);
        if(nums[mid] ==target){
            return left =mid;
        }else if(nums[mid]<target){
            left =mid+1;
        }else{
            right =mid-1;
        }
    }
     return left;
};
wangzehan123 commented 2 years ago

代码

Java Code:


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;
    }
}
CodeWithIris commented 2 years ago

Question

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

Note (Binary search)

Solution (C++)


class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1, ans = nums.size();
        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;
    }
};

Complexity

laofuWF commented 2 years ago 
# find left most index
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

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

        return left
zwang2244 commented 2 years ago

思路

binary search

代码

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

复杂度分析

zhangzhengNeu commented 2 years ago

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

ZacheryCao commented 2 years ago

Idea

Binary Search

Code:

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

Complexity:

Time: O(log N)\ Space: O(1)

Victoria011 commented 2 years ago

思路

找有序数列插入位置 -> binary search

代码

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

复杂度分析

Time Complexity: O(logN) N=len(nums)

Space Complexity: O(1)

YuyingLiu2021 commented 2 years ago 
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:

        #solution 1 
        # nums.append(target)
        # nums.sort()
        # return nums.index(target)

        #solution 2
        if nums[0] > target:
            return 0
        elif nums[-1] < target:
            return len(nums)
        else:
            for i in range(len(nums)):
                if nums[i] >= target:
                    return i
CoreJa commented 2 years ago

思路

我也没想到我从小到大居然没在LC上做过二分查找的题，今天正好借机会研究了下python里bisect的源码，分析了一波

代码

class Solution:
    # 朴素二分查找
    def searchInsert1(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        return left

    # 二分查找：更标准的板子(分为[left,mid]和[mid+1,right]，更合理)，和bisect包的源码类似。
    # - bisect_left的时候，
    #   - 去考虑`target`插到右边的情况，也就是`target>nums[mid]`：
    #     现在要缩左边界，`target`最终的结果一定不会为mid(因为是`bisect_left`，且已经比`nums[mid]`大)，所以缩小左边界不用考虑`mid`，`left=mid+1`
    #   - 而`target`插左边的时候：
    #     要缩右边界，即使`target`小于`nums[mid]`，但由于插的位置是`bisect_left`，有可能`target`还是除了`mid`以外的值都大，那最终结果依然有可能是mid，所以缩小右边界的时候不能忽略`mid`，所以`right=mid`
    # - 类似的，`bisect_right`的时候，
    #   - 去考虑`target`插左边的情况，也就是`target<nums[mid]`：
    #     现在要缩右边界，`target`的最终结果一定要考虑`mid`(因为是`bisect_right`，哪怕是比`nums[mid]`小，下标也要往右挪)。所以缩小右边界一定要考虑`mid`，`right=mid`
    #   - 而`target`插右边的情况：
    #     要缩左边界，就算`target`是等于(或$\geq$)`nums[mid]`了，但由于插的位置是`bisect_right`，下标必然要往右挪，所以缩小左边界不用考虑`mid`的情况，`left=mid+1
    def searchInsert2(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid
        return left

    # bisect：直接调api(源码和上面的类似)
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)
rzhao010 commented 2 years ago

Thoughts

Binary Search

  1. Found: return index
  2. Not Found: compare target with nums[start], if greater return (start + 1), or start

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) {
                mid = right;
            } else {
                mid = left;
            }
        }
        if (nums[left] == target) return left;
        if (nums[right] == target) return right;

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

Complexity

zhangzz2015 commented 2 years ago

思路

关键点

代码

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(target == nums[middle])
                return middle; 
            else if(target < nums[middle])
                right = middle-1; 
            else
                left = middle+1;                                             
        }

        // [right left] 
        return left;         
    }

};
xinhaoyi commented 2 years ago

35. 搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

思路一：二分法

说白了，我不管target到底存不存在，我要找的就是刚好比target要小的那个数的下标，这个下标 + 1就是我们要的下标，如果没找到，就说明target是这个nums里面最小的，

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        //说白了，我不管target到底存不存在，我要找的就是刚好比target要小的那个数的下标，这个下标 + 1就是我们要的下标
        //如果没找到，就说明target是这个nums里面最小的，
        int left = 0;
        int right = nums.length - 1;
        //处理一下特殊情况，如果target是里面最小的，也就是找不到比target还要小的数，此时特殊处理
        //注意，如果target就是nums[0]时也要特殊处理！
        if(target <= nums[0]){
            return 0;
        }
        while(left < right){
            int mid = (left + right + 1) / 2;
            if(nums[mid] >= target){
                right = mid - 1;
            }
            else{
                left = mid;
            }
        }
        return left + 1;
    }
}

复杂度分析

时间复杂度：$O(logn)$

空间复杂度：$O(1)$

Alexno1no2 commented 2 years ago 
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # # 使用bisect不管插入还是查找插入位置 应该都市log(n) 且只需要一行
        # return bisect.bisect_left(nums,target)

        # 二分查找 时间复杂度O(logn)
        start,end = 0,len(nums)-1
        while(start <= end):
            middle = start + ( end - start )//2
            if nums[middle] < target :
                start = middle + 1
            elif nums[middle] > target:
                end = middle - 1
            else:
                return middle
        return end + 1
ZhangNN2018 commented 2 years ago

思路

二分法

复杂度

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        leftt = 0
        right = len(nums) - 1
        while left <= right:
            middle = left + ( right-left) / 2
            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                return middle
        return right + 1
moirobinzhang commented 2 years ago

Code: 

public int SearchInsert(int[] nums, int target) {
        if (nums == null || nums.Length == 0)
            return -1;

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

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

            if (nums[mid] == target)
                return mid;

            if (nums[mid] > target)
                right = mid;
            else
                left = mid;
        }

        if (nums[left] >= target)
            return left;
        else if  (nums[left] < target && nums[right] >= target)
            return right;
        else 
            return right + 1;                
}
falconruo commented 2 years ago

思路: 二分法

复杂度分析:

代码(C++):

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

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

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

思路

二分查找

代码

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

复杂度分析

Yark-yao commented 2 years ago

思路

因为数组是升序的，可以使用二分法

代码

function searchInsert(nums: number[], target: number): number {

    return _searchInsert(nums,target,0,nums.length-1)
};

function _searchInsert(nums: number[], target: number,start:number,end:number){
    if(end-start <= 1 ){
        if(target <= nums[start]){
            return start
        } else if(target > nums[end]){
            return end+1
        }else{
            return end
        }
    }
    const middle = Math.floor((end-start)/2) +start

    if( target< nums[middle]){
        return _searchInsert(nums,target,start,middle)
    }else if(target === nums[middle]){
        return middle
    }else{
        return _searchInsert(nums,target,middle,end)
    }
}

复杂度

时间：O(LOGN) 空间：O(LOGN) 递归栈

spacker-343 commented 2 years ago

思路

二分

代码

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

复杂度

时间复杂度: O(logn) 空间复杂度: O(1)

CodingProgrammer commented 2 years ago

思路

二分法

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 二分法
        if (target <= nums[0]) return 0;
        int length = nums.length;
        if (target == nums[length - 1]) return length - 1;
        if (target > nums[length - 1]) return length;
        int left = 0, right = length - 1;
        while (left + 1 < right) {
            int mid = left + ((right - left) >> 1);
            if (target > nums[mid]) { // 往右去寻找
                left = mid;
            } else {
                right = mid;
            }
        }

        return nums[right] >= target ? right : left;
    }
}

复杂度

linyang4 commented 2 years ago

思路

二分法的变形

代码

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

复杂度

declan92 commented 2 years ago

思路
使用二分法寻找插入索引;
边界:target在尾部;
步骤模板 

while(l<r){
    if(nums[mid]==target){
        return mid;
    }if(nums[mid]>target){
        r = mid;
    }if(nums[mid]<target){
        l = mid;
    }
    return l;
}

java 

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

时间:O(logn)二分查找
空间:O(1)

hdyhdy commented 2 years ago

思路：经典二分法

func searchInsert(nums []int, target int) int {
    left :=0 
    right :=len(nums) - 1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] > target {
            right = mid - 1 
        }else if nums[mid] < target{
            left = mid + 1 
        }else {
            return mid
        }
    } 
    return left
}

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

MonkofEast commented 2 years ago

035. Search Insert Position

Click Me

Algo

What happens if we can't find the answer?

  1. Suppose target is bigger than the last single mid number. Then we set l += 1. We should return l.
  2. Suppose target is smaller than the last single mid nubmer. Then we set r -= 1 and left l untouched. We should also return l. So if we find no target, we should always return l.

Code

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

Comp

T: O(logN)

S: O(1)

Husky-Gong commented 2 years ago

Solution

Code

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;
    }
}

Complexity

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

tongxw commented 2 years ago

思路

二分基础知识，找不到目标时，最后的区间是[R, L]为目标值的下界和上界。这道题要返回上界。

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

        return l;
    }
}

TC: O(logN) SC: O(1)

iambigchen commented 2 years ago

思路

双指针，分别指向数组的首尾。取中间值，与目标值比较。如果大于目标值，说明右边指针需要左移。如果小于目标值，说明左指针需要右移

关键点

数组必须是顺序排列才可以

代码

JavaScript Code:


/**
 * @param {number[]} nums
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let l = 0
    let r = nums.length - 1
    while(l <= r) {
        let mid = (l + r) >> 1
        if (target < nums[mid]) {
            r--
        }
        if (target > nums[mid]) {
            l++
        }
        if (target == nums[mid]) {
            return mid
        }
    }
    return l
};

复杂度分析

令 n 为数组长度。

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

class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ l = 0 r = len(nums)

    while l < r:
        mid = (r + l) // 2

        if nums[mid] == target:
            r = mid

        elif nums[mid] > target:
            r = mid

        elif nums[mid] < target:
            l = mid + 1

    return l

思路： 二分法找左侧边界

Zhang6260 commented 2 years ago

JAVA版本

使用二分法

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

时间复杂度：O(logn)

空间复杂度：O(1)

wenjialu commented 2 years ago

Thought

Binary search

code

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

IF Found, return its idx; if not, return its insert place: left > right. return left

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

com

Time O(logn) Space O(1)