首页 > 编程语言 >二分算法查找列表中的目标值

二分算法查找列表中的目标值

时间:2024-03-22 15:58:43浏览次数:27  
标签:二分 输出 示例 int 查找 目标值 输入

题目要求:

给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。如果不是,返回索引按顺序插入时的位置。
(用二分法查找解决)
示例 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

from typing import List

class Solution:
    """
    二分法查找
    """
    def searchInsert(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high-low) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return low  # 没找到则返回其位置左边的下标, 即为它按顺序插入的位置

if __name__ == '__main__':
    res1 = Solution().searchInsert([1, 3, 5, 6, 7, 8, 10, 12], 3)
    print("res1结果是:%d" % (res1))
    res2 = Solution().searchInsert([1, 3, 5, 6, 10], 5)
    print("res2结果是:%d" % (res2))

执行结果:

res1结果是:1
res2结果是:2

 

标签:二分,输出,示例,int,查找,目标值,输入
From: https://www.cnblogs.com/lytester/p/18089659

相关文章