python面试题- 【二分法查找】给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引


前言

给定一个已排序的非重复整数数组和一个目标值,如果找到目标,则返回索引。如果不是,返回索引按顺序插入时的位置。

题目

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

二分法查找

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,二分查找的时候一定要是有序的数组。

二分法思想
1.首先从数组的中间元素开始查找,如果该元素正好是目标元素,则搜索结束,否则执行下一步。
2.如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤1的操作。
3.如果某一步数组为空,则表示找不到目标元素

如下图,数组中有目标元素,查找21

python面试题- 【二分法查找】给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引

如下图,数组中没有目标元素,查找70

python面试题- 【二分法查找】给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引

直到 low > high 查找失败

python面试题- 【二分法查找】给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引

python3 二分法查找

python3 代码示例

from typing import List


class Solution:
    """
    二分法查找
    """
    def searchInsert(self, nums: List[int], target: int) -> 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 = mid + 1
            else:
                right = mid - 1
        return left  # 没找到则返回其位置左边的下标, 即为它按顺序插入的位置


if __name__ == '__main__':
    res = Solution().searchInsert([1, 3, 5, 6], 7)
    print(res)

原创文章,作者:506227337,如若转载,请注明出处:https://blog.ytso.com/273927.html

(0)
上一篇 2022年7月13日
下一篇 2022年7月13日

相关推荐

发表回复

登录后才能评论