binary_search.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
# Interpreter version: python 2.7
# This work is licensed under a Creative Commons 3.0 Unported License
# (http://creativecommons.org/licenses/by/3.0/).
#
#= Functions & objects ========================================================


def binarySearch(low, high, test_fn):
	if test_fn(high):
		return high

	center = int((low + high) / 2)

	if test_fn(center):
		return binarySearch(center + 1, high, test_fn)
	else:
		return binarySearch(low, center - 1, test_fn)


#= Main program ===============================================================
if __name__ == '__main__':
	assert(binarySearch(0, 100, lambda x: x <= 20) == 20)