function i = locate(x, z, g)
% Usage: i = locate(x, z, g)
%
% This function finds i such that z is in [x(i), x(i+1)]
%
% input:
%	x	coordinates, x(1)<x(2)<...<x(length(x))
%	z	a point in [x(1), x(length(x))]
%	g	guess for the location, between 1 and length(x)-1
%		optional third argment
% output:
%	i	location such that z is in [x(i), x(i+1)]

n = length(x);
%
if nargin==3
    % try the initial guess
    if ((x(g)<=z) & (z<=x(g+1)))
	i = g;
	return
    % try a neighboring subinterval
    elseif ((g<n-1) & (x(g+1)<=z) & (z<=x(g+2)))
	i = g+1;
	return
    end
end
%
if z==x(n)
    i = n-1;
else
    % binary search
    left = 1;
    right = n;
    while (right > left+1)
	% x(left) <= z <= x(right)
	mid = floor((left+right)/2);
	if (z < x(mid))
	    right = mid;
	else
	    left = mid;
	end
    end
    i = left;
end