indx ← (fun ##.bsearch) range ⍝ Binary search. Range is a 2-item integer vector specifying a range of values. The operand function takes a scalar integer argument in this range and returns a boolean scalar result. By doing a "binary chop", bsearch finds the _lowest_ value in the range for which (fun value) is true. The values might typically be indices into a data stucture, for example a component file, where some property (fun value) is false for all components before a certain index, and true thereafter. For ex- ample, if 'tie' is a handle on a file whose components have been written in strictly chronological order (using only ⎕fappend), then the following express- ion finds the index of the first component written after timestamp 5.5e10: {5.5e10<3⊃⎕frdci tie ⍵} bsearch 2↑⎕fsize tie Note that the operand function, must be constructed so that it returns 0 for all values up to a certain point in the range, and 1 for those thereafter (~∨/1 0⍷ fun¨range), otherwise the result is unpredictable. The attraction of a binary search is that it makes only around 2⍟-/⌽range tests. This is important if the cost of the test is significant: perhaps it incurs a file access or some lengthy calculation. If the file in the above example had a million components, bsearch would find the index using only 20 or so calls on ⎕frdci. Examples: {⍵≥5} bsearch 3 7 5 {⍵≥9} bsearch 3 7 8 {⍵≥1} bsearch 3 7 3 Back to: contents Back to: Workspaces