Skip to content

Instantly share code, notes, and snippets.

@Phaeilo
Created August 22, 2013 14:06
Show Gist options
  • Save Phaeilo/6307642 to your computer and use it in GitHub Desktop.
Save Phaeilo/6307642 to your computer and use it in GitHub Desktop.
Iterator for doing binary searches.
#!/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()
@YorikSar
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment