From 438208bafad929f34d837e8f23f121d0bbe02e9a Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Thu, 11 Jun 2020 18:29:01 +0200 Subject: First commit MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- README | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 README (limited to 'README') diff --git a/README b/README new file mode 100644 index 0000000..aa692ca --- /dev/null +++ b/README @@ -0,0 +1,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. -- cgit v1.2.3-70-g09d2