шпаргалка

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



КАТЕГОРИИ:

Network | английский | архитектура эвм | астрономия | аудит | биология | вычислительная математика | география | Гражданское право | демография | дискретная математика | законодательство | история | квантовая физика | компиляторы | КСЕ - Концепция современного естествознания | культурология | линейная алгебра | литература | математическая статистика | математический анализ | Международный стандарт финансовой отчетности МСФО | менеджмент | метрология | механика | немецкий | неорганическая химия | ОБЖ | общая физика | операционные системы | оптимизация в сапр | органическая химия | педагогика | политология | правоведение | прочие дисциплины | психология (методы) | радиоэлектроника | религия | русский | сертификация | сопромат | социология | теория вероятностей | управление в технических системах | физкультура | философия | фотография | французский | школьная математика | экология | экономика | экономика (словарь) | язык Assembler | язык Basic, VB | язык Pascal | язык Си, Си++ |