Welcome, guest | Sign In | My Account | Store | Cart

Binary Search with the bisect Module (Python recipe) by Chris Perkins
ActiveState Code (http://code.activestate.com/recipes/389169/)

Writing a binary search algorithm is surprisingly error-prone. The solution: trick the built-in bisect module into doing it for you.

The documentation for bisect says that it works on lists, but it really works on anything with a __getitem__ method. You can exploit this fact to make bisect work in ways that you may not have thought of.

Example: Using a library that controls a digital video camera, I wanted to do a poor-man's auto-exposure. The goal is to find the exposure time, in milliseconds, that makes the mean pixel value about 128 (out of 0 to 255).

The trick is to create an object that "looks like" a list to the bisect module.

Python, 13 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import bisect

class AutoExp:
    def __init__(self, camera):
        self.camera = camera
    def __getitem__(self, index):
        self.camera.setshutter(index)
        im = cam.getframe() # returns a numarray array
        return im.mean()

def auto_expose(camera, target_mean=128):
    ms = bisect.bisect(AutoExp(camera), target_mean, 0, 1000)
    camera.setshutter(ms)
Tags: shortcuts

2 comments

Raymond Hettinger 19 years, 1 month ago  # | flag

Bisect not suited for control applications. This is an interesting and creative idea; however, for a control application such as this, a continuously-updated incremental approach would likely be better.

The nature of the video data is that the input stream changes over time and is subject to noise. Both factors tend to invalidate the assumption that the mean pixel value changes monotonically with the exposure time.

It may be better to continuously adjust the exposure up or down a percent or two at a time. That would result in smoother transitions, adaptation to changing inputs, and in stability against noise spikes (light/dark flashes, reflectivity, objects moving across the the field of view, digitization errors, etc).

Also, photographically speaking, the mean pixel value is problematic as an objective function -- both high key and low key scenes would end-up with improper exposures. A professional photographer with a spot meter would average the values from the brightest and darkest part of the scene so that all the values in between are captured -- the idea is to make the most of the camera's dynamic range.

Rene Hogendoorn 18 years, 11 months ago  # | flag

Masquerading as a "list" In this particular example, the lo, hi arguments are used to restrict the range of values to 0, 1000. A more general list-like object also needs an implementation of the __len__ member function.