various binary search algorithm including lower_bound upper_bound in python

binary_search.py

from __future__ import division


def binary_search(xs, target):
	"""
	type  : Listof[Val] * Val -> Int
	input : xs :: Sorted list
	        target :: Search target
	desp  : Return the index of the element in the list, -1 if the
	        element is not in the list
	"""
	l, r = 0, len(xs) - 1
	while l <= r:
		mid = (l + r) // 2
		if xs[mid] == target:
			return mid
		elif xs[mid] > target:
			r = mid - 1
		else:
			l = mid + 1
	return -1


def lower_bound(xs, target):
	"""
	type  : Listof(Val) * Val -> Int
	input : Same as binary_search
	desp  : Return the leftmost position when insert the target to the
	        position, the list remains in order


	invariant : target > xs[i] for all i < low
                xs[i]  >= target for all i > high
	"""
	low, high = 0, len(xs) - 1
	
	while low <= high:
		mid = (low + high) // 2
		if xs[mid] >= target:
			high = mid - 1
		else:
			low = mid + 1

	return low


def upper_bound(xs, target):
	"""
	type  : Listof(Val) * Val -> Int
	input : Same as binary_search
	desp  : Return the rightmost position when insert the target to the
	        position, the list remains in order


	invariant : target >= xs[i] for all i < low
                xs[i] > target for all i > high
	"""

	low, high = 0, len(xs) - 1
	while low <= high:
		mid = (low + high) // 2
		if xs[mid] > target:
			high = mid - 1
		else:
			low = mid + 1

	return low




def test_binary_search():
	assert(binary_search([], 10) == -1)
	assert(binary_search([1], 2) == -1)
	assert(binary_search([1], 1) == 0)
	assert(binary_search([1,1,1,2,2,2,3], 3) == 6)
	assert(binary_search([1,1,1,2,2,2,3], -1) == -1)

	return 'test of binary_search pass'


def test_lower_bound():
	assert(lower_bound([], 10) == 0)
	assert(lower_bound([1], 0) == 0)
	assert(lower_bound([1], 3) == 1)
	assert(lower_bound([1,1,1,2,2,2,3,3,3], 2) == 3)
	assert(lower_bound([1,1,1,2,2,2,3,3,3], 3) == 6)
	return 'test for lower_bound pass'


def test_upper_bound():
	assert(upper_bound([], 10) == 0)
	assert(upper_bound([1], 0) == 0)
	assert(upper_bound([1], 10) == 1)
	assert(upper_bound([1,1,1,2,2,2,3,3,3], 2) == 6)
	assert(upper_bound([1,1,1,2,2,2,3,3,3], 3) == 9)
	return 'test for upper_bound pass'


# We found a general pattern inthe procedure lower_bound and upper_bound, we can make some
# abstraction to generalize the idea to make code more concise

def bound_search_help(xs, target, pred):
	"""
	type : Listof(Val) * Val * (Val * Val -> Bool) -> Int
	desp : Generalization of the lower_bound and upper_bound procedure, which take a
	       function as third parameter, which take two value, and produce a boolean result.
	"""
	low, high = 0, len(xs) - 1
	while low <= high:
		mid = (low + high) // 2
		if pred(xs[mid], target):
			high = mid - 1
		else:
			low = mid + 1

	return low

def lower_bound_2(xs, target):
	return bound_search_help(xs, target, lambda x, y: x >= y)

def upper_bound_2(xs, target):
	return bound_search_help(xs, target, lambda x, y: x > y)


def test_lower_bound_2():
	assert(lower_bound_2([], 10) == 0)
	assert(lower_bound_2([1], 0) == 0)
	assert(lower_bound_2([1], 3) == 1)
	assert(lower_bound_2([1,1,1,2,2,2,3,3,3], 2) == 3)
	assert(lower_bound_2([1,1,1,2,2,2,3,3,3], 3) == 6)
	return 'test for lower_bound_2 pass'


def test_upper_bound_2():
	assert(upper_bound_2([], 10) == 0)
	assert(upper_bound_2([1], 0) == 0)
	assert(upper_bound_2([1], 10) == 1)
	assert(upper_bound_2([1,1,1,2,2,2,3,3,3], 2) == 6)
	assert(upper_bound_2([1,1,1,2,2,2,3,3,3], 3) == 9)
	return 'test for upper_bound_2 pass'


if __name__ == '__main__':
	print(test_binary_search())
	print(test_lower_bound())
	print(test_upper_bound())
	print(test_lower_bound_2())
	print(test_upper_bound_2())