Recursive Binary Search

Lab Python Intermediate 20 points

Read a sorted line of integers and a target. Print the index of the target found by a recursive binary search, or -1.

Input

Line 1: sorted integers. Line 2: target.

Output

An index or -1.

Example

Input

1 3 5 7 9 11
7

Output

Sample input available Sample output available

Editor

Python

Hints

Compare with the middle element and recurse into one half.

Solution explanation

Each call halves the search range, so it takes about log₂(n) steps.

Show solution

def search(nums, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return search(nums, target, mid + 1, hi)
    return search(nums, target, lo, mid - 1)


nums = list(map(int, input().split()))
target = int(input())
print(search(nums, target, 0, len(nums) - 1))

Output

Answer