"""BTVN: tìm kiếm, dữ liệu bản ghi, đo thời gian và căn bậc hai nguyên.

Python3:
  python3 g11-cs-chia-de-tri.py tim
  python3 g11-cs-chia-de-tri.py diem
  python3 g11-cs-chia-de-tri.py can 50
  python3 g11-cs-chia-de-tri.py do --repeat 5000
Dữ liệu tên/điểm là giả định. Đo riêng tìm kiếm trên cùng dãy đã sắp xếp.
"""
import argparse
import math
from time import perf_counter


def binarySearch(A, left, right, K):
    # A không giảm; khoảng chỉ số gồm cả left và right.
    if left > right:
        return -1
    mid = (left + right) // 2
    if A[mid] == K:
        return mid
    if A[mid] < K:
        return binarySearch(A, mid + 1, right, K)
    return binarySearch(A, left, mid - 1, K)


def binary_loop(A, K):
    left, right = 0, len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == K:
            return mid
        if A[mid] < K:
            left = mid + 1
        else:
            right = mid - 1
    return -1


def linearSearch(A, K):
    for i in range(len(A)):
        if A[i] == K:
            return i
    return -1


def find_record(DS, K):
    # DS giữ thứ tự không giảm theo điểm; trả một bản ghi phù hợp.
    names = [row[0] for row in DS]
    scores = [row[1] for row in DS]
    index = binarySearch(scores, 0, len(scores) - 1, K)
    if index < 0:
        return None
    return names[index]


def floorSqrt(n, start, end):
    # n nguyên không âm; lời gọi đầu là floorSqrt(n,0,n).
    if start == end:
        return start
    mid = (start + end) // 2
    if mid * mid == n:
        return mid
    if mid * mid < n:
        if (mid + 1) * (mid + 1) > n:
            return mid
        return floorSqrt(n, mid + 1, end)
    return floorSqrt(n, start, mid - 1)


def benchmark(repeat):
    rows = []
    for n in [10, 20, 50, 100]:
        A = list(range(n))
        K = n  # Không có trong A, để chạy tình huống phải tìm hết miền.
        start = perf_counter()
        checksum_linear = 0
        for _ in range(repeat):
            checksum_linear += linearSearch(A, K)
        linear_ms = (perf_counter() - start) * 1000 / repeat
        start = perf_counter()
        checksum_binary = 0
        for _ in range(repeat):
            checksum_binary += binarySearch(A, 0, len(A) - 1, K)
        binary_ms = (perf_counter() - start) * 1000 / repeat
        assert checksum_linear == checksum_binary == -repeat
        rows.append((n, linear_ms, binary_ms))
    return rows


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    modes = parser.add_subparsers(dest='mode', required=True)
    modes.add_parser('tim')
    modes.add_parser('diem')
    square = modes.add_parser('can')
    square.add_argument('n', type=int)
    timer = modes.add_parser('do')
    timer.add_argument('--repeat', type=int, default=5000)
    args = parser.parse_args()
    try:
        if args.mode == 'tim':
            A = [int(x) for x in input('Dãy số nguyên: ').split()]
            K = int(input('Số cần tìm: '))
            if any(A[i] > A[i + 1] for i in range(len(A) - 1)):
                raise ValueError('Dãy cần được sắp xếp không giảm.')
            print('Chỉ số:', binarySearch(A, 0, len(A) - 1, K))
        elif args.mode == 'diem':
            K = float(input('Điểm cần tìm: '))
            if not math.isfinite(K) or not 0 <= K <= 10:
                raise ValueError('Mẫu nhận điểm hữu hạn từ 0 đến 10.')
            DS = [['Mẫu A', 6.5], ['Mẫu B', 7.25],
                  ['Mẫu C', 8.0], ['Mẫu D', 9.5]]
            found = find_record(DS, K)
            print('Tên:', found if found is not None else 'không có')
        elif args.mode == 'can':
            if not 0 <= args.n <= 10**30:
                raise ValueError('Mẫu nhận n nguyên từ 0 đến 10^30.')
            print('Căn bậc hai nguyên:', floorSqrt(args.n, 0, args.n))
        else:
            if not 1 <= args.repeat <= 100000:
                raise ValueError('Số lần lặp cần từ 1 đến 100000.')
            print('n,tuan_tu_ms_moi_lan,nhi_phan_ms_moi_lan')
            for n, linear_ms, binary_ms in benchmark(args.repeat):
                print(f'{n},{linear_ms:.9f},{binary_ms:.9f}')
    except (ValueError, EOFError) as error:
        parser.exit(2, f'Dữ liệu không phù hợp: {error}\n')


if __name__ == '__main__':
    main()