Function Repository Resource:

IntegerBinarySearch

Efficiently find the transition point in a monotone binary predicate

Contributed by: Illia Voinovskyi

ResourceFunction["IntegerBinarySearch"][f,{min,max}]

performs a binary search for a boundary index in the integer range (min,max) where the binary predicate f:ℤ→{True,False} changes value.

ResourceFunction["IntegerBinarySearch"][f,{max}]

is equivalent to ResourceFunction["IntegerBinarySearch"][f,{1,max}].

Details

For monotone predicates (True values followed by False values, or vice versa), the function returns the unique index where the transition occurs.

The returned value is the index on the boundary where predicate evaluated to True.

ResourceFunction["IntegerBinarySearch"] returns All if f[l] and f[r] are both True, indicating the monotone predicate is identically True over the interval.

ResourceFunction["IntegerBinarySearch"] returns None iff[l] and f[r] are both False, indicating the monotone predicate is identically False over the interval.

For non-monotone predicates, the function returns any position where a transition occurs, as long as f[l]!=f[r].

Examples

Basic Examples (2)

Find the location of the first Fibonacci number bigger than 100:

In[1]:=

Out[1]=

Verify:

In[2]:=

Out[2]=

Scope (2)

If the monotone predicate does not contain a boundary, the function returns All or None. For example, all Fibonacci numbers are less than ∞:

In[3]:=

$ResourceFunction["IntegerBinarySearch"][ Fibonacci[#] <= \[Infinity] &, {1, 100}]$

Out[3]=

No Fibonacci numbers are negative:

In[4]:=

Out[4]=

IntegerBinarySearch returns the index on the boundary where the predicate was True. Find the location of the last Fibonacci number less than 30:

In[5]:=

Out[5]=

Find the location of the first Fibonacci number > 30:

In[6]:=

Out[6]=

IntegerBinarySearch[f,{max}] is equivalent to IntegerBinarySearch[f,{1,max}]:

In[7]:=

Out[7]=

In[8]:=

Out[8]=

Applications (4)

Find the first regular polygon with area larger than 3 and display it:

In[9]:=

Out[9]=

Find the first Fibonacci number that has 100 digits:

In[10]:=

$Fibonacci@ ResourceFunction["IntegerBinarySearch"][ Length@IntegerDigits@Fibonacci@# >= 100 &, {1, 10^3}]$

Out[10]=

Find the first n where the relative error of Stirling's factorial approximation is no bigger than one part in a million:

In[11]:=

$stirlingApprox[n_] := Sqrt[2 \[Pi] n] (n/E)^n$

In[12]:=

$ResourceFunction["IntegerBinarySearch"][ n |-> stirlingApprox[n]/n! >= 1 - 1/10^6, {2, 100000}]$

Out[12]=

Find out how many coin flips one should do in order to see 100 heads with 95% probability:

In[13]:=

$ResourceFunction["IntegerBinarySearch"][ n |-> Probability[x + 100 <= n, x \[Distributed] NegativeBinomialDistribution[100, 0.5]] >= 0.95, {1, 1000}]$

Out[13]=

Properties and Relations (1)

The function is essentially equivalent to ResourceFunction["BinarySearchBy"] and ResourceFunction["SortedPosition"]:

In[14]:=

Out[14]=

In[15]:=

Out[15]=

In[16]:=

$ResourceFunction["IntegerBinarySearch"][ Fibonacci[#] <= 10^60 &, {1, 5000}] // Timing$

Out[16]=

Possible Issues (3)

The function may not return expected results if the search range is not sufficiently large:

In[17]:=

$ResourceFunction["IntegerBinarySearch"][ Fibonacci[#] <= 10^60 &, {1, 100}]$

Out[17]=

Increasing the search interval solves the problem:

In[18]:=

$ResourceFunction["IntegerBinarySearch"][ Fibonacci[#] <= 10^60 &, {1, 10000}]$

Out[18]=

Binary search may fail on non-monotone functions:

In[19]:=

In[20]:=

Out[20]=

In[21]:=

Out[21]=

But if the interval bounds capture the flip, at least some position will be found:

In[22]:=

Out[22]=

In[23]:=

Out[23]=

If the predicate is not boolean, an error will occur:

In[24]:=

Out[24]=

Neat Examples (4)

Design the optimal threshold for a statistical binomial hypothesis test. In this example: α is a type I error (rejection of H0 when H0 is true), β is a type II error (rejection of Ha when Ha is true) when H0 is rejected if observed sample is >= q:

In[25]:=

$errors[n_, p0_, pa_, q_] := Module[{dist0, dista, \[Alpha], \[Beta]}, dist0 = BinomialDistribution[n, p0]; dista = BinomialDistribution[n, pa]; \[Alpha] = 1 - CDF[dist0, q - 1]; \[Beta] = CDF[dista, q - 1]; {\[Alpha], \[Beta]} ]$