% Loese das Problem min{ u(t) : t aus [t0, t1] } 
% mittels Bisektion mit Backtracking.
%
% Parameter:
% u		Zielfunktion mit u : R -> R
% du	Ableitung von u, R->R stetig in [t0, t1]
% ddu	Zweite Ableitung von u, wird nicht benoetigt, 
%			einfach @(x)0 angeben.
% t0,t1	Intervalgrenzen mit t0 < t1 und
%			du(t0) < 0, du(t1) > 0
%			falls du(t1) < 0 => Backtracking.
%
% epsilon	Genauerigkeitskonstante
%
% Rueckgabewerte:
% t		Minimalstelle
% k		Anzahl der Iterationen
%
% Das Verfahren berechnet nur die ersten 50 Iterationsschritte!!
%
function [t,k] = bisection(u, du, ddu, t0, t1, epsilon);

K = 50;
k = 0;

if abs(du(t0)) < epsilon
	t = t0;
	return;
end

if abs(du(t1)) < epsilon
	t = t1;
	return;
end

if du(t1) < 0
	% Backtracking
	for k = 0:K
		t = t0 + (t1 - t0)/2^k;
		if du(t) > 0
			t1 = t;
			break;
		elseif u(t) < u(t0)
			return;
		end
	end
end

% Bisection
for k = 1:K
	if ~(du(t0) < 0 && du(t1) > 0)
		warning('du(t0) < 0 und du(t1) > 0 nicht erfuellt.');
		[du(t0) du(t1)]
		break;
	end
	
	t = (t0 + t1) / 2;
	
	if abs(du(t)) < epsilon
		break;
	end;
	
	if (du(t0)*du(t) < 0)
		t1 = t;
	else
		t0 = t;
	end
end
