Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BinarySearch

Source Notebook

Find the position of a target value within a sorted array

Contributed by: Wolfram Staff

ResourceFunction["BinarySearch"][v,val]

gives the position of the last element of a sorted numeric vector v such that the element ei≤val.

Details

In ResourceFunction["BinarySearch"][v,val], v can have repeated elements.
The vector v must have at least two elements.
ResourceFunction["BinarySearch"] returns 0 if all elements ei>val.
For the sake of performance, ResourceFunction["BinarySearch"] does not check if the input list v is sorted, and can give an erroneous result for unordered lists.

Examples

Basic Examples (1) 

Find the position of the last element that is not greater than 6 in a list of numbers in ascending order:

In[1]:=
ResourceFunction["BinarySearch"][{1, 2, 5, 5, 7, 12}, 6]
Out[1]=

Properties and Relations (2) 

BinarySearch[v,val] returns 0 when all elements of v are greater than the val:

In[2]:=
ResourceFunction["BinarySearch"][{1, 1, 2}, -1]
Out[2]=

BinarySearch can be considerably faster for packed arrays:

In[3]:=
packed = Sort[RandomReal[{0, 100}, 100000]];
In[4]:=
RepeatedTiming[ResourceFunction["BinarySearch"][packed, 50]]
Out[4]=
In[5]:=
Developer`PackedArrayQ[packed]
Out[5]=
In[6]:=
unpacked = Developer`FromPackedArray[packed];
In[7]:=
RepeatedTiming[ResourceFunction["BinarySearch"][unpacked, 50]]
Out[7]=

Possible Issues (2) 

BinarySearch can give an erroneous result if the input vector is not sorted:

In[8]:=
ResourceFunction["BinarySearch"][{0, 2, 0}, 1]
Out[8]=

Use LengthWhile to find the position of first element less than 1 in an unsorted list:

In[9]:=
LengthWhile[{0, 2, 0}, # < 1 &]
Out[9]=

Version History

  • 1.0.1 – 28 June 2021
  • 1.0.0 – 09 March 2020

Related Resources

License Information