Kahendotsimine (binary search).
"Lõigu poolitamine" matemaatikas. On rakendatav kahel eeltingimusel:
1. vaadeldav struktuur on järjestatud
2. elemendid on indekseeritavad
O(log n)
/**
* Leida etteantud listist etteantud element kahendotsimise abil.
* @param a list.
* @param e otsitav element.
* @returns otsitava elemendi indeks või -1, kui elementi ei leidu.
*/
static public int otsi (List a, Comparable e) {
int j = -1;
int l = 0; // vasakpoolne otspunkt
int r = a.size() - 1; // parempoolne otspunkt
while (l <= r) {
j = (l + r) / 2;
if (e.compareTo ((Comparable)a.get (j)) == 0)
return j;
if (e.compareTo ((Comparable)a.get (j)) > 0)
l = j+1; // vasak otspunkt nihkub paremale
else
r = j-1; // parem otspunkt nihkub vasakule
};
return -1;
} // otsi lopp