Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 SearchOrderedList

Source Notebook

Search an ordered list at speed logarithmic in the length of a list

Contributed by: Michael Sollami

ResourceFunction["SearchOrderedList"][list]

gives the index of the first element of list that is True.

ResourceFunction["SearchOrderedList"][list,f]

gives the index of the first element of list for which f is True.

Details and Options

ResourceFunction["SearchOrderedList"] assumes the list is in sorted order according to OrderedQ and takes O(log n) time to find the index (as opposed to Position).
The second argument f is applied to elements of the list and should return True or False. The function f may instead return one of the three integers -1, 1, or 0 to indicate respectively that the desired point is to the left, to the right, or has been reached.
A fraction may be returned to indicate that an exact match was not found, but the desired element lies between two indices.

Examples

Basic Examples (3) 

Find the first integer which has at least 1050 partitions:

In[1]:=
AbsoluteTiming@ ResourceFunction["SearchOrderedList"][Range[10000], PartitionsP[#] > 10^50 &]
Out[1]=
In[2]:=
AbsoluteTiming@ FirstPosition[Range[10000], x_ /; PartitionsP[x] > 10^50]
Out[2]=

An exact match returns an integer and this happens if func returns zero on the desired element:

In[3]:=
ResourceFunction["SearchOrderedList"][Range[100], Sign[17 - #] &]
Out[3]=

In this case there is no match, so SearchOrderedList says it would have fallen between elements 91 and 92:

In[4]:=
space = Range[0, 20, 0.03]; res = ResourceFunction["SearchOrderedList"][space, Sign[E - #] &] // N
Out[4]=
In[5]:=
space[[Floor[res] ;; Floor[res] + 1]]
Out[5]=

Publisher

Michael Sollami

Version History

  • 1.0.0 – 18 March 2020

Related Resources

License Information