35.搜索插入位置

发表于 | 分类于
字数统计: 275 | 阅读时长 ≈ 1

题目描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

题解

思路

直接遍历，当不在数组范围内时，返回0或数组长度；在数组范围内时，返回索引值

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int searchInsert(int* nums, int numsSize, int target)
{
    if (target < nums[0])
        return 0;
    if (target > nums[numsSize - 1])
        return numsSize;
    int i;
    for (i = 0; i < numsSize; i++)
        if (target == nums[i])
            return i;
        else if (target > nums[i] && target < nums[i + 1])
            return i + 1;
    return -1;
}

思路

二分法

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)
        while low < high:
            mid = (low + high) // 2
            if nums[mid] < target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid
            else:
                return mid
        return low