% 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
% tic, quickfind(r(7654321),r), toc
% Have fun..
% oconnorp -at- ethz -dot- ch
Peter O'Connor (2021). quickfind (https://www.mathworks.com/matlabcentral/fileexchange/30112-quickfind), MATLAB Central File Exchange. Retrieved .
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.
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.
QUICKFIND might have a slight speed avantage, but surely not as flexible as MATLAB HISTC:
[~, loc] = histc(el,list)
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!