6 added 94 characters in body

However, the running time is $$O(length(S) * length(list))$$$$O(\operatorname{length}(S) \cdot \operatorname{length}(list))$$ - for larger $$S$$, this will get slow, fast.

The running time for Ordering should be $$O(n*log(n))$$$$O(n\log(n))$$ where $$n:=length(S) + length(list)$$$$n:=\operatorname{length}(S) + \operatorname{length}(list)$$. Running time for binary search is $$O(log(length(S)) * length(list))$$$$O(\log(\operatorname{length}(S)) \operatorname{length}(list))$$. If $$S$$ and $$list$$ are about the same size, this simplifies to $$O(n*log(n))$$$$O(n\log(n))$$, too - but with larger constants. Only if $$S$$ is much bigger than $$list$$, binary search will be faster.

However, the running time is $$O(length(S) * length(list))$$ - for larger $$S$$, this will get slow, fast.

The running time for Ordering should be $$O(n*log(n))$$ where $$n:=length(S) + length(list)$$. Running time for binary search is $$O(log(length(S)) * length(list))$$. If $$S$$ and $$list$$ are about the same size, this simplifies to $$O(n*log(n))$$, too - but with larger constants. Only if $$S$$ is much bigger than $$list$$, binary search will be faster.

However, the running time is $$O(\operatorname{length}(S) \cdot \operatorname{length}(list))$$ - for larger $$S$$, this will get slow, fast.

The running time for Ordering should be $$O(n\log(n))$$ where $$n:=\operatorname{length}(S) + \operatorname{length}(list)$$. Running time for binary search is $$O(\log(\operatorname{length}(S)) \operatorname{length}(list))$$. If $$S$$ and $$list$$ are about the same size, this simplifies to $$O(n\log(n))$$, too - but with larger constants. Only if $$S$$ is much bigger than $$list$$, binary search will be faster.

5 added 169 characters in body

For comparison, with this S, binary search takes much longer:

GeometricFunctionsBinarySearch[S, #] & /@ tst; // AbsoluteTiming


{64.0738, Null}

The running time for thisOrdering should be $$O(n*log(n))$$ where $$n:=length(S) + length(list)$$. Running time for binary search is $$O(log(length(S)) * length(list))$$. If $$S$$ and $$list$$ are about the same size, this simplifies to $$O(n*log(n))$$, too - but with larger constants. Only if $$S$$ is much bigger than $$list$$, binary search will be faster.

The running time for this should be $$O(n*log(n))$$ where $$n:=length(S) + length(list)$$. Running time for binary search is $$O(log(length(S)) * length(list))$$. If $$S$$ and $$list$$ are about the same size, this simplifies to $$O(n*log(n))$$, too - but with larger constants. Only if $$S$$ is much bigger than $$list$$, binary search will be faster.

For comparison, with this S, binary search takes much longer:

GeometricFunctionsBinarySearch[S, #] & /@ tst; // AbsoluteTiming


{64.0738, Null}

The running time for Ordering should be $$O(n*log(n))$$ where $$n:=length(S) + length(list)$$. Running time for binary search is $$O(log(length(S)) * length(list))$$. If $$S$$ and $$list$$ are about the same size, this simplifies to $$O(n*log(n))$$, too - but with larger constants. Only if $$S$$ is much bigger than $$list$$, binary search will be faster.

4 deleted 108 characters in body

# Small $$S$$

gives the same resultis very fast for your lists, and f[S] returns

{1, 2, 3, 4, 5}

which seems plausible to me.small $$S$$:

However, the running time is $$O(length(S) * length(list))$$ - for small $$S$$, this won't matter, but for larger $$S$$, something based on binary searchthis will be fasterget slow, fast.

# Large $$S$$

gives the same result for your lists, and f[S] returns

{1, 2, 3, 4, 5}

which seems plausible to me.

However, the running time is $$O(length(S) * length(list))$$ - for small $$S$$, this won't matter, but for larger $$S$$, something based on binary search will be faster.

# Small $$S$$

is very fast for small $$S$$:

However, the running time is $$O(length(S) * length(list))$$ - for larger $$S$$, this will get slow, fast.

# Large $$S$$

3 added 2018 characters in body
2 added 68 characters in body
1