File Exchange

image thumbnail

quickfind

version 1.2.0.0 (1.77 KB) by Peter O'Connor
Quickly finds an element in a sorted list. If not found, returns -index of next smaller element.

0 Downloads

Updated 10 Feb 2011

View Version History

View License

% loc=quickfind(el,list)
%
% Finds the index of an element el in a SORTED list really quick.
% loc is the location, found is a boolean indicating whether an exact match
% was found.
%
% It doesn't check if the list is sorted, because that would take O(N) time
% and this is meant to run in O(log(N)). If you give it an unsorted list,
% it will either return a zero, and error, or the wrong answer. It is
% guaranteed to stop though, which is nice.
%
% If you give it an element that's not in the sorted list, it interpolates,
% and sets found to false.
% Special cases: if it's smaller than the first element it returns zero.
% If it's bigger then the last element it returns length(list)+1, and of
% course found will be false.
%
% Example usage
% r=sort(rand(1,10000000));
% tic, quickfind(r(7654321),r), toc
%
% Have fun..
%
% Peter
% oconnorp -at- ethz -dot- ch

Cite As

Peter O'Connor (2021). quickfind (https://www.mathworks.com/matlabcentral/fileexchange/30112-quickfind), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (3)

Peter O'Connor

There's probably a faster search function implemented in mex out there, I didn't look very hard.

It just does a generalized version of binary search, where it spits into 100 intervals instead of 2 on each iteration. Reason being that each time a while loop iterates in matlab it has to go through all the overhead of the interpretor, so it's to a certain extent better to reduce iterations and do small linear searches in each.

The advantage over histc is just really when you need to search big lists of like a billion elements repeatedly. histc has the overhead of first checking to see if the list is sorted. This function trusts you to be a grown-up and sort your own lists.

Gary

I'm confused by this. If the list is sorted, why wouldn't you use a binary search? For my simple test, a FEX binary search is considerably faster than this. I'm not meaning to be critical - just wondering what problem this addresses that a binary search doesn't.
A=1:10000;
tic
for indx=1:10000
loc=quickfind(indx,A);
end
quickfindTime=toc

Bruno Luong

QUICKFIND might have a slight speed avantage, but surely not as flexible as MATLAB HISTC:

[~, loc] = histc(el,list)

MATLAB Release Compatibility
Created with R2010b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!