时间戳

首页 > 解决方案 > 二进制搜索模板 Leetcode，它的含义是什么？

binary-search - 二进制搜索模板 Leetcode，它的含义是什么？

问题描述

我在 leetcode 中找到了一个二进制搜索模板

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 是二进制搜索的高级形式。它用于搜索需要访问当前索引及其在数组中的直接右邻索引的元素或条件。”

我正在努力理解上述信息的含义。在通常的二进制搜索中，权利将是

right = len(nums) - 1 # before while loop

right = mid - 1 # inside while loop

而while循环将是

while left <= right:

标签： binary-search

解决方案

您正在对数组执行二进制搜索。假设数组有 100 个元素。

#    left, right = 0, len(nums)
left = 0, right = 99
#        mid = (left + right) // 2
mid = 49

#        elif nums[mid] < target:
We need to move right.
#            left = mid + 1
left = 50 and right = 99
#        else:
We need to move left.
#            right = mid
Left = 0, right = 49

推荐阅读