时间戳

首页 > 解决方案 > 二分查找中的元素邻居

python - 二分查找中的元素邻居

问题描述

我在 leetcodes Explore 中阅读了两个二分搜索模板 - LeetCode

标准模板 I

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

总结关键属性：

  1. 二分搜索的最基本和基本形式

  2. 可以在不与元素的邻居比较（或使用其周围的特定元素）的情况下确定搜索条件

  3. 不需要后处理，因为在每个步骤中，您都在检查是否找到了元素。如果你到达终点，那么你知道元素没有找到

参考属性2：

可以在不与元素的邻居比较（或使用其周围的特定元素）的情况下确定搜索条件

我不明白它的想法。

有条件while left <= right，怎么能说出来without comparing to the elements neighbors

模板二

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    # Post-processing:
    # End Condition: left == right
    if left != len(nums) and nums[left] == target:
        return left
    return -1

关键属性：

  • 一种实现二分搜索的高级方法。
  • 搜索条件需要访问元素的直接右邻
  • 使用元素的右邻判断条件是否满足，决定是向左还是向右
  • 保证搜索空间在每一步至少为 2 大小
  • 需要后处理。当您剩下 1 个元素时，循环/递归结束。需要评估剩余元素是否满足条件。

是什么element，不是中间吗？

我可能会陷入困境，请您提供提示以提供帮助吗？

标签： python

解决方案

我同意@knh190，这里的描述很不清楚，我已经阅读了几次以了解他的想法。专注于代码更有用。

您可以以自己的方式理解代码，而不是遵守他的规则。

还有一个建议，一个算法的实现太多了，所以选择最熟悉的版本，你会被太多的变体版本弄糊涂，也许只是一些编码爱好者。或者，它确实是最好的性能和最简洁的解决方案，但它并不适合你。

对于第一个问题，“存在条件while left <= right，如何陈述without comparing to the elements neighbors”：
我认为他的陈述在这里模棱两可，我认为您已经明白了他的想法，因为while left <= right，所以我们不需要without comparing to the elements neighbors。
相比之下，你可以看到第二个版本while left < right，所以他应该比较循环外的元素邻居nums[left] == target。

对于第二个问题，“元素是什么，不是mid吗？”： element表示当前成员 in nums， in 循环，它指的是 'nums[mid]'，而外循环element指的是nums[left]

我希望我能明白他的意思，你的意思，让你明白我的意思。:)

推荐阅读