## On Dichotomic Divide-and-Conquer Algorithms

March 12, 2016 | Tips | en

From what I observed, InDesign scripters do not naturally resort to the dichotomic (or binary) search algorithm when it comes to find a numeric solution to problems as wide as adjusting frame bounds to some constraint, determining an optimal text size, or simply accessing a needle in the haystack. Yet the binary search approach is nearly always the best. So let's make it more popular…

Here is the deal: you need to fit a `TextFrame`

to its content without changing its height. In other words, taking into account the original state of the object, you want to find the minimal width that still prevents the frame from overflowing.

The naive approach is to reduce the length bit by bit until you reach the limit. But the reduction step must be small enough to meet the required precision, say **0.5pt**, which leads to a huge number of steps when the solution is far from the initial state. Here is the picture:

In the above example 148 steps are needed to reach the optimal width. Note that at least two InDesign DOM commands are sent at each step: the first for changing the frame width (i.e. its `geometricBounds`

), the second for checking the `overflows`

flag.

Now consider the binary search algorithm. It begins by testing the middle value, that is the half width. If the value is too small (i.e. the text frame overflows), then the process continues on the upper half, otherwise it continues on the lower half. At each iteration the search interval is divided by two, which somehow *eliminates* half of the possible values. In mathematical terms, *W* being the initial width and *P* being the required precision (expressed in the same unit) there are `N = W/P`

possible results. Then, on average, the step-by-step method will reach the solution in `N/2`

iterations, while the binary search will reach it in `log2(N)+1`

iterations.

In my example `W=400`

, `P=0.5`

so `N=800`

. Hence the naive method involves on average 400 iterations (actually, 148) while the divide-and-conquer process only involves `|log2(800)+1| = 11`

iterations (actually, 10), as shown in the animation below:

**Note.** — A possible implementation of this **fitHorizontal** routine is provided in the entry “Fit Text Frame to Content (supporting multicolumn)” of the ISFR series.

## Implementation Notes

Binary search algorithms are easy to implement. They only require you backup the *current* bounds of the search interval. At each iteration the middle term is calculated and takes the place of either the lower or the upper bound depending on some condition. I often use a `[min,max]`

array `a`

to represent the in-progress interval. The middle value `mid`

is therefore `(a[0]+a[1])/2`

. Now suppose that a `checkState()`

function returns either `0`

or `1`

, where `1`

means that `mid`

is too high at the current stage—for example: `+myFrame.overflows`

. One can then use `a[checkState()]=mid`

to update the array and divide the interval accordingly.

Here is a skeleton:

var findOptimalValue = function(...) { // Settings // --- const MIN = ..., MAX = ..., PRECISION = ...; // Initialization // --- var a = [MIN,MAX], mid; // Dichotomic search // --- while( a[1]-a[0] > PRECISION ) { mid = (a[0]+a[1])/2; a[checkState()] = mid; } // Conclusion // --- // Depending on your requirements, return mid, a[0], or a[1] };

A basic example is provided in this maximizePointSize function. The goal was to find the maximum point size for the text contained in a given frame. As you will see, the dichotomic algorithm has many applications in adjusting stuff with respect to metric constraints (dimensions, point size, tracking, scaling, etc.)

See also the entry “Fit Horizontal Text Scale to Frame” in ISFR #8. It provides a very abstract snippet for various *optimal adjustment* problems.

Here is a more sophisticated use of the divide-and-conquer process. The following function returns a fractional representation of a decimal number within `[0..1]`

. It uses the Stern–Brocot binary tree to find quickly the optimal result, as suggested in this discussion.

var fractionalForm = function(/*0..1*/x, xMin,xMax,n,d,mn,md) { const EPSILON = .00001; if( (xMin=x-EPSILON) < 0 ) return '0'; if( (xMax=x+EPSILON) > 1 ) return '1'; n = [0,1]; d = [1,1]; while( 1 ) { mn = n[0] + n[1]; md = d[0] + d[1]; if( md*xMax < mn ) { n[1] = mn; d[1] = md; continue; } if( md*xMin > mn ) { n[0] = mn; d[0] = md; continue; } return mn + '/' + md; } }; alert( fractionalForm(.66666667) ); // => 2/3

Even if the above routine does not strictly fit our dichotomic search pattern, you may notice that it involves a very similar iteration process.

## Comments

simple and effective.

Thanks Marc.

better is to use "recherche dichotomique table des puissances de 2"

Hi Marc,

Thanks for your interesting post. Partitioning algorithms are powerful indeed -- QuickSort and the binary array search come to mind.

Your post inspired me to check some algorithms I had lying around to see how dramatic the difference is between the naive method (which I sometimes use(d) when lazy) and the binary method. Unsurprisingly, the difference is enormous. But I noticed an interesting side effect that I hadn't realised before but which makes sense when you think of it: when you fit text to a frame using the naive method, you never get as good a fit as with the binary method.

In the short test I did, I had an overset frame with 28-points text. Using the naive method, sizing down in by 0.1 pts takes 69 steps to fit the text, and the text ends up in 21.1 pts. Setting it down by 0.01 pts takes 685 steps, and the result was 21.15-pt text.

The binary method, on the other hand, performs as follows: resizing by 0.1 pts takes 9 steps, the text ends up in 21.156 pts. Resizing by 0.01 pts takes 15 steps, and here, too, the text ends up as 21.156 pts. So not only is the binary method much more efficient, it's also more precise. The difference (21.150 pts vs 21.156 pts) isn't enormous, but the point is that you get that precision for free.

Peter

Thanks Peter for your rich comment. I'm pleased that my articles are read and appreciated by experienced programmers.

About the gain in precision I'm not sure you can technically interpret things as you do. On average, given a required precision, both the naive and the binary methods will meet the requirement. From that standpoint it can't be said that one method is more accurate than the other.

It may seem that the dichotomic search reaches more precise results, because dividing the interval again and again brings out fractional values that sound more fine-tuned. But I think it's nothing but a feeling.

Consider a stupid example. Let the initial interval be [0,100] and the exact solution be 99. Suppose we want a precision < 0.5. The naive method will reach the exact solution (in two steps) while the binary search will stop at 99.21875 (after several steps.) In this case the step-by-step algorithm wins in terms of actual precision.

What we know is that the binary search is on average dramatically faster. But I don't see why on average it would be closer to the exact solution (when the same precision is required.) Maybe you're right though. I just lack the proof of your conjecture.

Best,

Marc