2008-06-08

Binary Search libary for LabVIEW

LabVIEW provides a built-in 1D search function which is a linear search implementation.  That is the algorithm check a value from the very first element of an given array, then 2nd,... until it finds a matched value.  It is O(n) algoritm. Thus it is likely useless for large arrays.



If you have a sorted array, binary search is useful.  This algorithm checks the value in the middle of given array to determine the expected value is located in the first half or last half of the array.  Then it check the value in the middle of the first/last half portion, .... until it finds the value.  It is O(log n) algorithm.





Satoru Takabayashi has implemented the algorithm in Ruby; Ruby/BSearch and I ported it for LabVIEW.




First, you need to create an VI to compare two values in advance of using the library.  The VI accepts two variants A and B, and returns the result of (A-B).  The VI should simply perform subtract B from A if you want to search a numeric array.  The VI, however, will be more complicated if you want to search an array of cluster.  Note that the VI must return 0 if matched.



Cmpint






Okey, now you are ready to search with, say, BianarySearch.lvlib:Range.vi.  The example below shows the VI returns the index of first occurence of "2" and and 1+ the index of the last; i.e. 1 and 3 respectively.



Bsearchexample




download BinarySearch-0.1.zip