Linear vs Binary Search

Lab Python Intermediate 20 points

Read a sorted line of integers and a target. Print the index found by a linear search and by an iterative binary search, plus the number of comparisons each made (−1 index when missing).

Input

Line 1: sorted integers. Line 2: target.

Output

Two lines: index comparisons

Example

Input

1 3 5 7 9 11 13 15 17 19
17

Output

8 9
8 3

Sample input available Sample output available

Editor

Python

Hints

Binary search keeps halving the range [lo, hi].

Solution explanation

Linear search checks every item (O(n)); binary search needs about log₂ n checks (O(log n)) but requires sorted data.

Show solution

nums = list(map(int, input().split()))
target = int(input())

idx, steps = -1, 0
for i, x in enumerate(nums):
    steps += 1
    if x == target:
        idx = i
        break
print(idx, steps)

lo, hi = 0, len(nums) - 1
idx, steps = -1, 0
while lo <= hi:
    mid = (lo + hi) // 2
    steps += 1
    if nums[mid] == target:
        idx = mid
        break
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(idx, steps)

Output

Answer