Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BinarySearchBy

Source Notebook

Find the position of a target value within an array sorted after applying a function

Contributed by: Wolfram Staff

ResourceFunction["BinarySearchBy"][list,val,f]

gives the position of the last element ei in list such that f[ei]≤val.

Details and Options

ResourceFunction["BinarySearchBy"][list,val,f] is equivalent to BinarySearch[f/@list,val].
Elements of f/@list must be numeric.
ResourceFunction["BinarySearchBy"][list,val,f] assumes that f/@list is arranged in ascending order and can give an erroneous result if it is not.

Examples

Basic Examples (1) 

Find the position of the last pair whose first element is not greater than 5:

In[1]:=
ResourceFunction[ "BinarySearchBy"][{{1, a}, {3, b}, {5, c}, {6, d}}, 5, First]
Out[1]=

Properties and Relations (1) 

BinarySearchBy is essentially equivalent to the resource function BinarySearch after applying f to elements of list:

In[2]:=
list = SortBy[RandomReal[{0, 1}, {10, 2}], Last]
Out[2]=
In[3]:=
ResourceFunction["BinarySearchBy"][list, .5, Last]
Out[3]=
In[4]:=
BinarySearch[Last /@ list, .5]
Out[4]=

Possible Issues (2) 

BinarySearchBy[list,val,f] can give an erroneous result if elements obtained by applying f to list are not arranged in ascending order:

In[5]:=
unsorted = {"ab", "c", "de", "fgh"};
In[6]:=
ResourceFunction["BinarySearchBy"][unsorted, 2, StringLength]
Out[6]=

Get the result after sorting the list:

In[7]:=
SortBy[unsorted, StringLength]
Out[7]=
In[8]:=
ResourceFunction["BinarySearchBy"][%, 2, StringLength]
Out[8]=

Version History

  • 1.0.0 – 09 March 2020

Related Resources

License Information