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


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 (2023). 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
Find more on Shifting and Sorting Matrices in Help Center and MATLAB Answers

Community Treasure Hunt

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

Start Hunting!
Version Published Release Notes

changed it so it interpolates when an element isn't found, and added a second output indicating whether the exact match was found.

fixed a thing where it wouldn't find the last element