Binary Search for Algortihmic Toolbox

binary_search.py

# Uses python3
import sys
import random

def binary_search(a, x):
    left, right = 0, len(a)

def linear_search(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

def checkInput(n, min, max):
    if n<min or n>max:
        return True
    return False

def checkParameters(n, sorted, m, searchNumbers):
    # check that n and capacity fit the parameters
    if (n<1 or n>10000):
        sys.exit(0)
    if (m<1 or m>10000):
        sys.exit(0)

    # check that there are enough elements
    if n != len(sorted):
        sys.exit(0)
    if m != len(searchNumbers):
        sys.exit(0)

    # check that the list is sorted in ascending order
    for i in range(len(sorted)-2):
        if sorted[i] > sorted[i+1]:
            sys.exit(0)

    #check that the values in the arrays fit the parameters
    for i in range(n):
        if checkInput(sorted[i], 1, 1000000000):
            sys.exit(0)
    for j in range(m):
        if checkInput(searchNumbers[j], 1, 1000000000):
            sys.exit(0)

def binarySearch(numbers, key, low, high):
    if high<low:
        return -1
    midpoint = low + (high-low)//2
    if key == numbers[midpoint]:
        return midpoint
    elif key < numbers[midpoint]:
        return binarySearch(numbers, key, low, midpoint-1)
    elif key > numbers[midpoint]:
        return binarySearch(numbers, key, midpoint+1, high)
    else:
        return -1


def stressTest(arraySize, testSize):
    sampleSequence = random.sample(range(1, arraySize), (arraySize - 1))
    sampleSequence.sort()
    testSequence = random.sample(range(1, testSize), (testSize - 1))
    print(sampleSequence)
    print(testSequence)
    for key in testSequence:
        searchResult =  binarySearch(sampleSequence, key, 0, (len(sampleSequence)-1))
        print(searchResult, end = ' ')
    print("\n")


if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n = data[0]
    m = data[n + 1]
    sorted = data[1 : n + 1]
    searchNumbers = data[n+2:]
    # checkParameters(n, sorted, m, searchNumbers)
    for x in searchNumbers:
        print(binarySearch(sorted, x, 0, (len(sorted)-1)), end = ' ')

#
# if __name__ == '__main__':
#     # stress Test
#     stressTest(int(sys.argv[1]), int(sys.argv[2]))