#!/usr/bin/env python3

import random
import sys


def main():
    n = 100
    v = 0
    maxval = 99
    if len(sys.argv) > 1:
        v = int(sys.argv[1])
    if len(sys.argv) > 2:
        n = int(sys.argv[2])
    if len(sys.argv) > 3:
        maxval = int(sys.argv[3])
    a = []
    for i in range(n):
        a.append(random.randint(0, maxval))
    binsertionsort(a)
    checkorder(a)
    print(str(a))
    i = bsearch(a, v)
    if i == -1:
        print(str(v), " not found")
    else:
        print(str(v), " in position ", str(i))


def checkorder(arr):
    for i in range(len(arr)-1):
        if arr[i] > arr[i+1]:
            raise ValueError("Wrong order: " + str(arr[i]) + " > " +
                             str(arr[i+1]) + " index " + str(i))


def bsearch(arr, value):
    n = len(arr)
    if n == 0:
        return -1
    if value > arr[n - 1]:
        return -1
    left = 0
    right = len(arr)
    while left <= right:
        mid = int((left + right) / 2)
        x = arr[mid]
        if value == x:
            return mid
        else:
            if value > x:
                left = mid + 1
            else:
                right = mid - 1
    return -1


def binsertionsort(arr):
    if len(arr) < 2:
        return
    for i in range(1, len(arr)):
        b = arr[i]
        left = 0
        right = i
        while left < right:
            mid = int((left + right) / 2)
            if b < arr[mid]:
                right = mid
            else:
                left = mid + 1
        arr[left+1:i+1] = arr[left:i]
        arr[left] = b


if __name__ == '__main__':
    main()