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.

577 Downloads

Updated 10 Feb 2011

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 .

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!