# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

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

Contributed by:
Michael Sollami

ResourceFunction["SearchOrderedList"][ gives the index of the first element of | |

ResourceFunction["SearchOrderedList"][ gives the index of the first element of |

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.

Find the first integer which has at least 10^{50} partitions:

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

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

In[3]:= |

Out[3]= |

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

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

- 1.0.0 – 18 March 2020

This work is licensed under a Creative Commons Attribution 4.0 International License