blob: 65396bf730998e47d02016ff1f10cdd333309ec5 (
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 in another
sorted list their position or if missing where they
ought to be inserted. Both lists must allow random access.
Complexity:
n = number of elements in target list
m = number of elements to locate
Time complexity: O(m S(n/m) + m)
S = time complexity function of underlying 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 February 2013.
|
