SHPORA.net :: PDA

[ Back ]

"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