File Exchange

## quickfind

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

Updated 10 Feb 2011

% 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!