Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.6 kB
0
Indexable
Never
def search_br_index(nums, left, right):
    print('search_br_index', right <= left, left, right)
    if len(nums[left:right]) <= 1:
        return len(nums) // 2
    if nums[right - 1] < nums[right - 2]:
        return right - 1
    mid = (left + right) // 2
    if nums[mid] < nums[mid - 1]:
        return mid
    else:
        search_br_index(nums, left, mid)
        search_br_index(nums, mid, right)


def search_target(nums, target, left, right):
    print('search_target', right <= left, left, right)
    if right <= left:
        return -1
    mid = (left + right) // 2
    print('nums[mid] == target', nums[mid] == target)
    if nums[mid] == target:
        print(1, mid)
        return mid
    elif target > nums[mid]:
        print(2)
        search_target(nums, target, mid, right)
    else:
        print(3)
        search_target(nums, target, left, mid)


def broken_search(nums, target) -> int:
    br_index = search_br_index(nums, 0, len(nums))
    print(br_index)
    if nums[br_index] == target:
        return br_index
    elif target > nums[br_index] and br_index != len(nums) - 1:
        index = search_target(nums, target, br_index, len(nums))
        print('search_target(nums, target, br_index, len(nums))', index)
        return index
    else:
        index = search_target(nums, target, 0, br_index + 1)
        print('search_target(nums, target, 0, br_index + 1)', index)
        return index


def test():
    arr = [1, 2, 3, 5, 6, 7, 9, 0]
    result = broken_search(arr, 3)
    print(result)
    assert result == 2

test()