Iterator for doing binary searches.

binsearchit.py

#!/usr/bin/env python
 
# The MIT License (MIT)
# 
# Copyright (c) 2013 Philip Huppert
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy of
# this software and associated documentation files (the "Software"), to deal in
# the Software without restriction, including without limitation the rights to
# use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
# the Software, and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
# FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
# COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
# IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

"""
binsearchit.py:
Iterator for doing binary searches. This is just a quick and dirty prototype,
feel free to build upon or extend it. See the main method at the end of this
file for a usage example.
"""

__author__    = "Philip Huppert"
__copyright__ = "Copyright 2013, Philip Huppert"
__license__   = "MIT"
__version__   = "1.0"

class BinSearchIt:
    """Iterator for doing binary searches."""

    def __init__(self, low=0, high=1000000):
        self.low = low
        self.high = high
        self.got_feedback = True

    def __iter__(self):
        return self

    def next(self):
        if not self.got_feedback:
            raise Exception("No feedback given for binary search")

        if self.high > self.low:
            self.current = int((self.low+self.high)/2)
            self.got_feedback = False
            return self.current
        else:
            raise StopIteration

    def too_high(self):
        """Tell the iterator that its last output was too high."""
        self.high = self.current
        self.got_feedback = True

    def too_low(self):
        """Tell the iterator that its last output was too low."""
        self.low = self.current
        self.got_feedback = True

    def found(self):
        """Tell the iterator that its last output was our target."""
        self.high = self.low = self.current
        self.got_feedback = True


if __name__ == "__main__":
    # Example usage:
    bs = BinSearchIt()
    tgt = 12345

    for i in bs:
        if i < tgt:
            print "Too low: ", i
            bs.too_low()
        elif i > tgt:
            print "Too high:", i
            bs.too_high()
        else:
            print "Found:   ", i
            bs.found()

Why not use generator here? Like this:

def binsearchgen(low=0, high=1000000):
    while high > low:
        current = int((high + low) / 2)
        feedback = yield current
        if feedback > 0:
            high = current
        elif feedback < 0:
            low = current
        else:
            break