File Exchange

image thumbnail

Fast Binary Search

version 1.4 (6.57 KB) by

Binary Search algorithm to search for values in a sorted array. Written in C (.mex) for speed.

3 Downloads

Updated

View License

** Description :
mex function that performs the binary search algorithm to find "item(s)"
(the values to be searched for) in some pre-sorted "data" vector.
By default, the algorithm returns the index of the first instance of each "item"
(if there are multiple copies found), and returns the index of the closest item
if the item(s) are not found (although these behaviors can be changed
with appropriate optional input parameters.)

Note : by default, the algorithm does not check whether the input data is sorted (since
that would be an O(N) procedure, which would defeat the purpose of the
algorithm. If the input data is not sorted, the output values will be incorrect.

** Matlab call syntax:
pos = binarySearchMatlab(data, items, [dirIfFound], [dirIfNotFound], [checkIfSorted_flag])

** Matlab compile command:
mex binarySearch.c

** Input: This function requires (pre-sorted) reference data vector "data",
as well as a second input, "items" to search for. "items" can be any size.

** Output : "pos" is the same size as the input "items".

* Optional input arguments: 'dirIfFound' and 'dirIfNotFound' specify
the function's behavior if the items are not found, or if multiple
items are found: (Supply an empty vector [] to leave as the default.)
Note, if you like, you can change the default behavior in each case by
modifying the DEFAULT values in the #define section below.

dirIfFound specifies the function's behavior if *multiple* copies of the
value in "items" are found.
-1, or 'first' : [default] the position of the *first* occurence of 'item' is returned
+1, or 'last' : the position of the *last* occurence of 'item' is returned.
0, or 'any' : the position of the first item that the algorithm discovers is found
(ie. not necessarily the first or last occurence)

dirIfNotFound specifies the behavior if the value in "items" is *not* found.
0, or 'exact' : the value 0 is returned.
-1, or 'down' : the position of the last item smaller than 'item' is returned.
+1, or 'up' : the position of the first item greater than 'item' is returned.
2, or 'closest' : [default], the position of the *closest* item closest to 'item' is returned
0.5, or 'frac' : the function returns a *fractional* value, indicating, the relative position
between the two data items between which 'item' would be located if it was in the data vector.
(eg if you are searching for the number 5 (and "data" starts off with [ 2, 3, 4, 7,...], then
the algorithm returns 3.333, because 5 is 1/3 of the way
between the 3th and the 4th element of "data".

checkIfSorted_flag
By default, this program is set *not* to check that the input data vector is sorted. (although you can change this by setting the defined CHECK_IF_INPUT_SORTED_DEFAULT as 1)
However, if you provide a non-empty 5th argument the input data will be checked.
(You might use this, for example, while debugging your code, and remove it later
to improve performance)

Comments and Ratings (4)

Uri

Uri (view profile)

Giuseppe

David, could you post your modifications here? thanks.

David

David (view profile)

compact & stable implementation! nice feature with fuzzy or fractional relation.
for my purpose i added a check for values off interval.
thanks! david

David

David (view profile)

Updates

1.4

- fixed a memory leak
- added out-of-bounds check to the binary search core.
- allow for 'data' and 'items' to be single or double-precision

1.1

Minor bug fixed & a few typos corrected.

MATLAB Release
MATLAB 7.11 (R2010b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video