aboutsummaryrefslogtreecommitdiffstats
path: root/README
blob: aa692cade256e7a71d6062f079e051b9095db70d (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Binary multisearch

Description:
	Given a sorted list of unique items, find their in another
	list 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.