skinner consulting

professional | programming | privacy | jobs | personal | what's new | faq | links | contact
 
 
You are here: Home > Professional > Downloads > Binary Search

Binary Search

This implements the traditional binary search algorithm in native 4D code, to find a value within a sorted array. When compiled, Binary Search is faster than FIND IN ARRAY if the array holds more than a few hundred elements; the larger the array, the greater the speed difference. The breakeven point appears to be around 200 (not considering the overhead of sorting the array, if you had not done so of your own accord). Interpreted, it is always much slower than FIND IN ARRAY.

Input parameters are pointers to the array and to a target value. Output is a longint: the index number of the matching array element, or -1 if the target value is not in the array. (Binary Search also returns -1 if the array and target are of incompatible data types, in this case the system variable OK is set to 0.) It does not handle two-dimensional arrays or wildcards, for reasons that should be obvious.

Because the underlying algorithm is in the public domain, the source code is directly editable (all methods are public) and the component is distributed under the GNU public license. Executive summary: the component is free for you to use and distribute as you wish, provided that (a) you do not claim credit for writing it, (b) you do not charge for distributing it, (c) everyone who receives it from you has these same rights in full, and (d) you notify me of any improvements you make.

Binary Search is distributed as a component, to be installed in your structure files using 4D Insider version 6.7 or higher. The Macintosh version is a Stuffit Expander archive, the Windows version is a ZIP archive. Both are 8Kb in size. Documentation exists as Explorer comments, and as comments in the methods themselves.

The current release is 1.1, dated 23.05.2003. Consider this a gamma version: it runs well but there may still quite large bugs in it.

 


http://www.skinnerconsulting.com/downloads/4d/binarysearch/binSrch.html
Copyright © John Skinner, 2003. All rights reserved.
Last updated 2003.05.24