剑指 Offer II 068. 查找插入位置

剑指 Offer II 068. 查找插入位置 #

  • 标签:数组、二分查找
  • 难度:简单

题目大意 #

给定一个排好序的数组 nums,以及一个目标值 target

要求:在数组中找到目标值,并返回下标。如果找不到,则返回目标值按顺序插入数组的位置。

解题思路 #

二分查找法。利用两个指针 leftright,分别指向数组首尾位置。每次用 leftright 中间位置上的元素值与目标值做比较,如果等于目标值,则返回当前位置。如果小于目标值,则更新 left 位置为 mid + 1,继续查找。如果大于目标值,则更新 right 位置为 mid - 1,继续查找。直到查找到目标值,或者 left > right 值时停止查找。然后返回 left 所在位置,即是代插入数组的位置。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left = 0
        right = 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
本站总访问量  次  |  您是本站第  位访问者