Обговорення:Двійкове дерево пошуку
Найсвіжіший коментар: Дядько Ігор у темі «Двійковий пошук» 16 років тому
| Ця стаття є частиною Проєкту:Комп'ютерні науки (рівень: невідомий) | ||
|---|---|---|
|
Мета проєкту — створення якісних та інформативних статей на теми, пов'язані з інформатикою і комп'ютерними науками. Ви можете покращити цю статтю, відредагувавши її, а на сторінці проєкту вказано, чим ще можна допомогти. Учасники проєкту будуть вам вдячні. | |
| ??? | Цю статтю ще ніхто не оцінив за шкалою оцінок статей Проєкту:Комп'ютерні науки. | |
Чим допомогти:
| ||
 | Цю статтю перейменовано з Бінарне дерево пошуку за рішенням спільноти (див. на сторінці Вікіпедія:Перейменування статей/Бінарне дерево пошуку → Двійкове дерево пошуку) Повторне виставлення статті на перейменування при відсутності вагомих підстав для перегляду попереднього рішення може розглядатися як порушення правила ВП:НДА (див. розділ «Не випробовуйте на міцність»). Нове обговорення можливе лише у випадку, якщо старі аргументи не були враховані або з'явились нові. |
Двійковий пошук
[ред. код]взявся перекладати ru:Двоичный поиск>> Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини (див. двійкове дерево), залежно від результату порівняння.
Трудомісткість алгоритму .
- Приклад на C++
int BinarySearch(int A[], int left, int right, int val, int &place)
{
int mid; //middle point between left and right
int found; //1- value found; 0- value still not found
int found=0;
while((left<=right) && (!found)){
mid=(left+right)/2; // compute middle point
// check value against maiddle point and adjust bounds accordingly.
if(val==A[mid]) {
place=mid;
found=1;
}
else if (val<A[mid]) right=mid-1;
else left=mid+1;
}
return (found);
}
<< І що, маємо статтюна цю тему, бо хотів знайти власне двійкове дерево, а знайшов статтю. Чи, може, я не правий?--Albedo @ 09:30, 8 лютого 2006 (UTC)
- Ні. Наведена функція - пошук у масиві, а стаття про побудову дерева і пошук у ньому. Дерево краще, якщо не знаємо наперед кількість елементів. Дядько Ігор 16:53, 11 січня 2008 (UTC)
На ілюстрації ж не двійкове дерево, хіба ні?