# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1355189120 21600
# Node ID 0f98bcb5bd3f8d3d1b5f29ac4ca6d532c5cfa509
# Parent  aea27d10dd188fdb108826d6ee26c34654167192
Added the bisection() function for Ch 3.3 exercise 3.

diff -r aea27d10dd18 -r 0f98bcb5bd3f ch3ex3.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch3ex3.py	Mon Dec 10 19:25:20 2012 -0600
@@ -0,0 +1,27 @@
+"""Chaper 3.3, exercise 3.
+
+Write a function called bisection that takes a sorted list and a target value
+and returns the index of the value in the list if it's there, or None if it's
+not.
+
+"""
+
+def bisection(a, item):
+    """Returns the index of item in the sorted list a if it exists or None if
+    not.
+
+    Finds the "rightmost" item if it exists.
+
+    """
+    lo = 0
+    hi = len(a)
+
+    while lo < hi:
+        mid = (lo + hi) // 2
+        if item < a[mid]:
+            hi = mid
+        else:
+            lo = mid + 1
+
+    n = lo - 1
+    return a[n] if n >= 0 and a[n] == item else None