Chapter 6, exercise 2, #4. Wrote a program to output the center column of
a rule 30 CA as a stream of bytes. It is very slow though. It has to run a very
long time to produce enough data for dieharder. Committing it now but will have
to let it run overnight or something to generate a large file.
| author |
Brian Neal <bgneal@gmail.com> |
| date |
Sun, 13 Jan 2013 16:24:00 -0600 |
| parents |
cfb7f28678c7 |
| children |
|
| rev |
line source |
|
bgneal@11
|
1 """Chaper 3.3, exercise 3.
|
|
bgneal@11
|
2
|
|
bgneal@11
|
3 Write a function called bisection that takes a sorted list and a target value
|
|
bgneal@11
|
4 and returns the index of the value in the list if it's there, or None if it's
|
|
bgneal@11
|
5 not.
|
|
bgneal@11
|
6
|
|
bgneal@11
|
7 """
|
|
bgneal@11
|
8
|
|
bgneal@11
|
9 def bisection(a, item):
|
|
bgneal@11
|
10 """Returns the index of item in the sorted list a if it exists or None if
|
|
bgneal@11
|
11 not.
|
|
bgneal@11
|
12
|
|
bgneal@11
|
13 Finds the "rightmost" item if it exists.
|
|
bgneal@11
|
14
|
|
bgneal@11
|
15 """
|
|
bgneal@11
|
16 lo = 0
|
|
bgneal@11
|
17 hi = len(a)
|
|
bgneal@11
|
18
|
|
bgneal@11
|
19 while lo < hi:
|
|
bgneal@11
|
20 mid = (lo + hi) // 2
|
|
bgneal@11
|
21 if item < a[mid]:
|
|
bgneal@11
|
22 hi = mid
|
|
bgneal@11
|
23 else:
|
|
bgneal@11
|
24 lo = mid + 1
|
|
bgneal@11
|
25
|
|
bgneal@11
|
26 n = lo - 1
|
|
bgneal@33
|
27 return n if n >= 0 and a[n] == item else None
|
|
bgneal@33
|
28
|
|
bgneal@33
|
29
|
|
bgneal@33
|
30 if __name__ == '__main__':
|
|
bgneal@33
|
31 a = [0, 2, 4, 5, 7, 22]
|
|
bgneal@33
|
32
|
|
bgneal@33
|
33 assert bisection(a, 0) == 0
|
|
bgneal@33
|
34 assert bisection(a, 22) == len(a) - 1
|
|
bgneal@33
|
35 assert bisection(a, 4) == 2
|
