5.0

5.0 | 2 ratings Rate this file 26 Downloads (last 30 days) File Size: 6.57 KB File ID: #30484

Fast Binary Search

by

 

21 Feb 2011 (Updated )

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

| Watch this File

File Information
Description

** 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)

MATLAB release MATLAB 7.11 (R2010b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (4)
24 Apr 2012 Uri  
17 Nov 2011 Giuseppe

David, could you post your modifications here? thanks.

30 Aug 2011 David

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

30 Aug 2011 David  
Updates
22 Feb 2011

Minor bug fixed & a few typos corrected.

03 May 2013

- 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

Contact us