How do I perform a binary search of a presorted array?

I would like to perform a binary search of an array of elements in MATLAB, based on some logical condition. The find function, while useful, performs a linear search with runtime complexity O(n).

I would like to know if there is an alternative procedure using the equivalent of a 'binary search' type of method that performs the same in O(log(n)), to determine if an element is contained within an array.

Answer 1

[MathWorks Support Team]

You may find the function ismember useful in this scenario, since it performs a binary search along with other error checking.

"ismember" first ensures that the input array is pre-sorted using the

issorted

 method, as well as performing other input argument checks. It will also handle NaN arguments.

Release R2014a (version 8.3) and before:

The core binary search method in the function "ismember" is outsourced for performance reasons to two MEX files: "ismembc" and "ismembc2".

% ISMEMBC  - S must be sorted - Returns logical vector indicating which 
% elements of A occurs in S, used when only output argument TF is specified
% ISMEMBC2 - S must be sorted - Returns a vector of the locations of 
% the elements of A occurring in S.  If multiple instances occur,
% the last occurrence is returned, used when TF and LOC output arguments are specified          
%
% Check for NaN values - NaN values will be at the end of S,
% but may be anywhere in A.

To perform a fast binary search of your array, you can use these functions directly in MATLAB without all the other error checking present in "ismember" with the following syntax.

% A = elements to search for
% S = set of elements to be searched within
% tf = logical array the same size as A, indicating if elements were found in S
% loc = array the same size as A, indicating the index of the elements in S, or 0 if not found
%
tf = ismembc(A,S);
loc = ismembc2(A,S);

Please note that since "ismembc" and "ismembc2" are MEX file interfaces, input argument checking and general good numerical programming practices are presumed on the part of the user to avoid segmentation violations and other system crashes when using them.

Release R2014b (version 8.4) and after:

There is a built-in helper function called from within "ismember". This helper function can be called directly to get both outputs: indicating if the elements are found, and indicating where they are found.

% Use builtin helper function ISMEMBERHELPER:
% [LIA,LOCB] = ISMEMBERHELPER(A,B) Returns logical array LIA indicating
% which elements of A occur in B and a double array LOCB with the
% locations of the elements of A occuring in B. If multiple instances
% occur, the first occurence is returned. B must be already sorted.

This can be called with the following syntax:

% A = elements to search for
% S = set of elements to be searched within
% tf = logical array the same size as A, indicating if elements were found in S
% loc = array the same size as A, indicating the index of the elements in S, or 0 if not found
%
% To just get indication if elements are contained
tf = builtin('_ismemberhelper',A,S);
% To get both the indication that it is contained, and the indices of the elements
[tf, loc] = builtin('_ismemberhelper',A,S);

Note that "ismembc" and "ismembc2" are still available to be called directly. As with "ismembc" and "ismembc2", input checking may not be done in "_ismemberhelper". Ensuring the input is correct and does not contain NaNs would then have to be done by the user to avoid errors and possible crashes.

Also please note that these are all internal, undocumented functions. Their behavior may change without warning in a future release of MATLAB.

[Cam Salzberger]

Hello Archit,

Thanks for pointing out that this answer was out of date. I've updated the answer to include more information about recent versions of MATLAB.

[Walter Roberson]

To emphasize slightly: do not just call ismember() directly, because the check it does for sorted order is a linear check. Assuming the data is already sorted, call directly into the membership helper routines.

[Sterling Baird]

Seems like ismemberhelper & ismembc2 now output double arrays for the 2nd and 1st arguments, respectively. i.e.

[~,loc] = builtin('_ismemberhelper',1:10,5);
loc = ismembc2(1:10,5)

loc =

     0     0     0     0     1     0     0     0     0     0

suggesting that the functionality of ismembc2 has changed. Is there a new MEX helper function that returns the indices rather than a logical array?

Edit: maybe this is how the functionality has been all along, and I just misunderstood.