leecode-35. 搜索插入位置

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：sarizzm time:2020/12/29 0029

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

print(Solution().searchInsert([1,3,5,6], 7)==4)
print(Solution().searchInsert([1,3,5,6], 0)==0)
print(Solution().searchInsert([1,3,5,6], 2)==1)
print(Solution().searchInsert([1,3,5,6], 5)==2)
print(Solution().searchInsert([1], 0)==0)

执行用时：36 ms, 在所有 Python3 提交中击败了85.27%的用户

内存消耗：15.2 MB, 在所有 Python3 提交中击败了11.56%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/