Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.8 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 -1
    mid = (left + right) // 2
    if nums[mid] < nums[mid - 1]:
        return mid
    left = search_br_index(nums, left, mid)
    right = search_br_index(nums, mid, right)
    if left != -1:
        return left
    elif right != -1:
        return right
    else:
        return len(nums) // 2


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


def broken_search(nums, target) -> int:
    if nums[0] == target:
        return 0
    if nums[len(nums) - 1] == target:
        return len(nums) - 1
    br_index = search_br_index(nums, 0, len(nums))
    # print('br_index', br_index)
    if br_index == -1:
        br_index = len(nums) // 2
    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)
        # print('search_target(nums, target, 0, br_index + 1)', index)
        return index


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

test()