quickfind

Quickly finds an element in a sorted list. If not found, returns -index of next smaller element.

Description

% 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

• MATLAB release: MATLAB 7.11 (2010b)

[Bruno Luong]

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

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

[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

[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.