Бинарный поиск расширенный шаблон объяснения - PullRequest
Новая
       4

Бинарный поиск расширенный шаблон объяснения

0 голосов
/ 14 марта 2020

Я изучал шаблон бинарного поиска II на Leetcode. https://leetcode.com/explore/learn/card/binary-search/126/template-ii/937/

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

Говорят, что ключевым атрибутам этого шаблона, включая

  • Условию поиска, необходим доступ к непосредственному правому соседу элемента
  • Используйте правого соседа элемента, чтобы определить, выполнено ли условие, и решить, * go слева или справа
  • Размер Поиска Гарантий по крайней мере 2 на каждом шаге

I не понимал, как код «непосредственно обращается к элементу доступа к элементу права доступа» или использует его, чтобы «определить, выполнено ли условие и решить, * go влево или вправо".

Как это работает?

...