Неправильная логика условия в задаче с поиском в массиве

Question

https://ru.stackoverflow.com/a/1306764/461186

Помогите исправить Логику условия в этом ответе. Код красивый, но при входных данных когда array[middle] > target, код переход в else: left = middle -1

PS оставлю здесь также свой рабочий код. Просто мне понравился код, на который ссылка выше, поэтому и хотел его сделать полностью рабочим

def binary_search(array, target, left=0, right=None):
    if right is None:
        right = len(array) - 1
    if not array:
        return -1
    mid = (left + right + 1) // 2
    if array[mid] == target:
        return mid
    if left == right:
        return -1
    if array[0] < array[mid]:
        if target >= array[0]:
            if target > array[mid]:
                return binary_search(array, target, mid, right)
            return binary_search(array, target, left, mid - 1)
        return binary_search(array, target, mid, right)
    if target < array[0]:
        if target < array[mid]:
            return binary_search(array, target, left, mid - 1)
        return binary_search(array, target, mid, right)
    return binary_search(array, target, left, mid - 1)


def broken_search(array, target):
    return binary_search(array, target, 0, len(array) - 1)

Answer 1

def BSinBroken (arr, value):
    lo = 0
    hi = len(arr)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == value:
            return mid

        if arr[lo] <= arr[mid]: #сортирован левый
            if arr[lo] <= value <= arr[mid]:
                hi = mid - 1   #ищем в нём
            else:
                lo = mid + 1   #ищем в правом
        else:
                if arr[mid] <= value <= arr[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
    return -1

Если хотите один раз назначать пределы, то объедините условия, но условие будет очень громоздким и нечитабельным.

БЛОГ НА HUSL

Неправильная логика условия в задаче с поиском в массиве

Ответы (1 шт):