Krimskrams - Folgen durchlaufen
Lösung zu Aufgabe 6 mit Programm 24, Seite 21
K. Hug 2010-08-05, 2011-09-30, 2012-03-01

public static int linearSearch (Object[] f, Object a) {
	int res = -1;
	for (int i = 0; i < f.length; i++) {
		if (f[i].equals(a))
			return (res = i);
	}
	return res;
}

Korrektheit:
Vorbedingungen ergänzen!

public static int linearSearch (Object[] f, Object a) {
	assert f != null : "precondition";
	// assert for each i in 0..f.length-1 : f[i] != null : "precondition";
	// "a == null" poses no problem.
	int res = -1;
	for (int i = 0; i < f.length; i++) {
		assert f[i] != null : "precondition";
		if (f[i].equals(a))
			return (res = i);
	}
	return res;
}

Schwäche 1:
Die Bedeutung von "-1" als "not found" gehört zur Schnittstelle,
ein Kommentar in der Implementation genügt nicht!
Besser:
public static final int notFound = -1;

Schwäche 2:
In "return (res = i)" ist die Zuweisung an res sinnlos,
da res beim return vom Laufzeitkeller entfernt wird.
Zurückgegeben wird der Wert von i, also genügt "return i".

Diese Schwächen beseitigen: 

public static int linearSearch (Object[] f, Object a) {
	int i;
	for (i = 0; i < f.length; i++) {
		if (f[i].equals(a)) {
			return i;
		}
	}
	return notFound;
}

Schwäche 3:
Die for-Schleife ist als Bedingungsschleife missbraucht.
Deshalb in eine äquivalente while-Schleife umformen und 
Nachbedingungen für nächsten Schritt ergänzen:

public static int linearSearch (Object[] f, Object a) {
	int i = 0;
	while (i < f.length) {
		if (f[i].equals(a)) {
			assert i < f.length && f[i].equals(a) : "postcondition";
			return i;
		}
		i++;
	}
	assert i >= f.length : "postcondition";
	return notFound;
}

Schwäche 4:
Die Lösung ist unstrukturiert, weil aus dem Schleifenrumpf gesprungen wird.
Gemeinsame Nachbedingung als Disjunktion der einzelnen Nachbedingungen hinschreiben,
daraus die Fortsetzungsbedingung und die strukturierte Lösung konstruieren:

public static int linearSearch (Object[] f, Object a) {
	int i = 0;
	while (i < f.length && !f[i].equals(a)) {
		i++;
	}
	assert i >= f.length || (i < f.length && f[i].equals(a)) :
							"postcondition";
	if (i < f.length) {
		return i;
	} else {
		return notFound;
	}
}

Schwäche der strukturierten Lösung:
"i < f.length" muss nach der Schleife noch einmal hingeschrieben und
ausgewertet werden, d.h. die statische Komplexität und die Laufzeitkomplexität
sind etwas höher als bei der unstrukturierten Lösung.

Schleifennacharbeit mit bedingtem Ausdruck vereinfachen:

public static int linearSearch (Object[] f, Object a) {
	int i = 0;
	while (i < f.length && !f[i].equals(a)) {
		i++;
	}
	assert i >= f.length || (i < f.length && f[i].equals(a)) :
							"postcondition";
	return i < f.length ? i : notFound;
}

Schwäche 5:
Name der Funktion bezeichnet Algorithmus statt Ergebnis.
Besseren Namen minIndex einsetzen;
Nachbedingung, die zur Konstruktion hilfreich, weglassen:

public static int minIndex (Object[] f, Object a) {
	int i = 0;
	while (i < f.length && !f[i].equals(a)) {
		i++;
	}
	return i < f.length ? i : notFound;
}

Vorbedingungen und Konstantendefinition für notFound wieder dazuschreiben:

public static final int notFound = -1;

public static int minIndex (Object[] f, Object a) {
	assert f != null : "precondition";
	// assert for each i in 0..f.length-1 : f[i] != null : "precondition";
	int i = 0;
	while (i < f.length && !f[i].equals(a)) {
		i++;
	}
	return i < f.length ? i : notFound;
}

Jeder Informatik-Student im dritten Semester sollte fähig sein,
alle Lösungen ineinander zu transformieren!