1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#!/usr/bin/python3
 
# SI 335: Computer Algorithms
# Unit 1
 
from math import floor
import random
 
def linearSearch(A, x):
    i = 0
    while i < len(A) and A[i] < x:
        i = i + 1
    if i < len(A) and A[i] == x: return i
    else: return 'NOT FOUND'
 
 
def binarySearch(A, x, left=0, right=None):
    if right is None: right = len(A) - 1
    while left < right:
        middle = floor((left + right) / 2)
        if x <= A[middle]:
            right = middle
        elif x > A[middle]:
            left = middle+1
    if A[left] == x: return left
    else: return 'NOT FOUND'
 
 
def gallopSearch(A, x):
    i = 1
    while i < len(A) and A[i] <= x:
        i = i * 2
    left = floor(i / 2)
    right = min(i, len(A)) - 1
    return binarySearch(A, x, left, right)
 
 
# This is provided for testing purposes.
def randomSortedArray(size, maxval):
    return sorted(random.sample(range(maxval), size))
 
def searchTest():
    searchAlgs = [linearSearch, binarySearch, gallopSearch]
    allgood = True
    data = randomSortedArray(10000, 10000000)
    i = random.randrange(len(data))
    val = random.choice(data)
    while val in data:
        val += 1
    for alg in searchAlgs:
        good = (
            alg(data, -10) == 'NOT FOUND' and
            alg(data, data[i]) == i and
            alg(data, data[0]) == 0 and
            alg(data, data[-1]) == len(data)-1 and
            alg(data, val) == 'NOT FOUND'
        )
        if not good:
            print("FAILED CHECK for", alg.__name__)
            allgood = False
    return allgood
 
if __name__ == '__main__':
    if searchTest():
        print("All checks passed!")