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.
|
