Mercurial > public > think_complexity
annotate ch3ex3.py @ 24:5c2c4ce095ef
A stab at the L(p)/L(0) plot.
I still don't quite get how the graphs in the Watts and Strogatz paper were
generated. My results have basically the same shape, but don't converge to 0.
I'm not sure how this is possible if the rewire function does not remove edges.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Thu, 03 Jan 2013 18:41:13 -0600 |
| parents | 0f98bcb5bd3f |
| children | cfb7f28678c7 |
| 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@11 | 27 return a[n] if n >= 0 and a[n] == item else None |