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)]
#
# inputs:
#       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
    endif
endif
#
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;
        endif
    endwhile
    i = left;
endif

endfunction # locate