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

120 views (last 30 days)
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.

Accepted Answer

MathWorks Support Team
MathWorks Support Team on 15 Nov 2021
Edited: MathWorks Support Team on 16 Nov 2021
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
 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.
  5 Comments
Shlomo Geva
Shlomo Geva on 26 Feb 2022
Edited: Shlomo Geva on 26 Feb 2022
A comment with respect to searching sorted arrays that may contain duplicates.
It seems that the function ismembc2() returns the index of the matching entry it finds with the largest index if there are duplicates. It will not identify all of the matching entries if the array is searched for a value which happens to have duplicates. If all duplicate locations are required then the caller needs to do some extra work after calling ismembc2()
example:
>> x=[1, 2, 3, 3, 3, 3, 3, 6]; ismembc2(3,x)
ans =
7
>>
It found a 3, but obviously 7 is not the index of the first entry equal to 3, or even the entry that a strict binary search will find. If duplicates exist then the caller needs to work backwards from index 7 to collect the other matching entries if exist.
>>

Sign in to comment.

More Answers (1)

Ritik Raj
Ritik Raj on 19 Apr 2022
% 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);
  1 Comment
Walter Roberson
Walter Roberson on 19 Apr 2022
How does this differ from what was posted in https://www.mathworks.com/matlabcentral/answers/92533-how-do-i-perform-a-binary-search-of-a-presorted-array#answer_101883 ?

Sign in to comment.

Products


Release

No release entered yet.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!