aboutsummaryrefslogblamecommitdiffstats
path: root/README
blob: 74529d31a801e2575c4268fc87bf91f78733a7f7 (plain) (tree)
1
2
3
4
5


                  

                                                            


















                                                                                                     
Binary multisearch

Description:
	Given a sorted list of unique items, find in another
	sorted list their position or if missing where they
	ought to be inserted. Both list must allow random access.

Complexity:
	n = number of elements in target list
	m = number of element to locate

	Time complexity: O(S(n) + m)
		S = time complexity function of underlaying search algorithm,
			e.g. S(n) = O(log n) in average case for binary search given O(1) comparison.

	Auxiliary space complexity:
		List return version:	O(m)
		Online version:     	O(log m)

Notes:
	In online version, positions for elements are returned in
	arbitrary (deterministic) order, rather than sequential.

I wrote this algorithm back in Feburary 2013.