loc=quickfindstr(el,list)

function loc=quickfindstr(el,list)
% loc=quickfindstrstr(el,list)
%
% Finds the index of an element el in a SORTED list of strings
%
% 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,
% its behaviour is undefined
%
% If you give it an element that's not in the sorted list, it returns -1
%
% Example of usage:
%
% lis={'aa','zz','fdf','fdeeg','aaff'}
% lis=sort(lis); % must be sorted !
% quickfindstr('fefe',lis)  % returns -1 (not found)
% quickfindstr('zz',lis) % returns 2
%
% time comparison for a long list (about 150000 elements)
% tic; strmatch(totr{end},totr,'exact'); toc -> 1.30562 seconds
% tic; quickfindstr(totr{end},totr); toc -> 0.002985 seconds (about 400
% times faster)
% 
% by Manel Soria 
% manel -dot- soria -at- gmail -dot- com
% LLOP - grup Obert de Programari Lliure
% ETSIAT - UPC
%
% Adapted fom quickfind by Peter O'Connor,
% http://www.mathworks.es/matlabcentral/fileexchange/30112-quickfind
% Peter
% oconnorp -at- ethz -dot- ch
% uses strcmpc by S. Helsen 23-09-96, you can download it from:
% http://www.mathworks.es/matlabcentral/fileexchange/3987-compare-strings-c-convention/content/Strcmpc.m
% 


% If not in bounds, enforce the "negative nearest lower index" rule
if strcmpc(el,list{1})<0
    loc=-1; 
    return;
elseif strcmpc(el,list{end})>0
    loc=-1; 
    return;
elseif  strcmpc(el,list{1})==0
    loc=1;
    return;
end


n=100; 
% n should be at least 3 to work  Test show it's more or less the same from 
% 30 to 500, then it starts sucking for bigger numbers.
    
st=1;
en=numel(list);
while true
    
    ix=ceil(linspace(st,en,n));

    for i=2:length(ix)
        if strcmpc(el,list{ix(i)})<=0
            break;
        end
    end
    
    if strcmpc(el,list{ix(i)})==0
        loc=ix(i);
        return;
    else
        st=ix(i-1); en=ix(i);        
        if (en-st)<2
            % It's not in the list, or the list ain't sorted
            loc=-1;
            return;
        end            
    end    
end



end