Обговорення:Двійковий пошук
Матеріал з Вікіпедії — вільної енциклопедії.
На скільки я зрозумів — алогоритм є рекурсивним, і краще б його приклад виглядав у рекурсивній формі. Чи не так? --vityok 17:39, 16 грудня 2006 (UTC)
- будь який цикл є рекурсивним? то чому м не писати всі цикли рекурсією? ---- Ілля 18:07, 16 грудня 2006 (UTC)
def binary_search (arr, el)
if len(arr) > 0 then
middle := len(arr)/2
if el = arr[middle] then
return True
else if el < arr[middle] then
return binary_search(subarr(arr, 0, middle), el)
else
return binary_search(subarr(arr, middle, len(arr)), el)
else
return False
чи правильно я його зрозумів? --vityok 18:38, 16 грудня 2006 (UTC)
- Твоє питання я розумію так, що ти не знав раніше як працює двійковий пошук? Невже?
- Вірна твоя реалізація чи містить помилку можна сказати лише знаючи представлення масивів та логіку subarr ---- Ілля 18:54, 16 грудня 2006 (UTC)
Ще є цікава річ. Хтось допоможе знайти статті на сайті Борланда де описується проблеми швидкодії T*Dataset.Find* Суть у тому, що вони мають проблеми з індексами - і маємо в результаті лінійний пошук. Ги-Ги ця проблема поширена :) ---- Ілля 19:02, 16 грудня 2006 (UTC)
[ред.] Приклад на Objective Caml
Його ще слід перевірити на правильність роботи, але, в моєму простому випадку, здається, що працює:
(*
s_list a list of values to perform search on
left index of a sublist start
right index of a sublist end ((length s_list) - 1)
what a value to look for
*)
let rec binary_search s_list left right what =
let middle = (left + (right - left)/2) in
let middleVal = nth s_list middle in
if middleVal = what then
middle
else (
if left >= right then
-1
else (
if middleVal > what
then binary_search s_list left (middle-1) what
else binary_search s_list (middle+1) right what));;
Ця функція є рекурсивною (з хвостовою рекурсією). Відповідно до її сигнатури, може застосовуватись (для будь-яких списків, для елементів яких визначений оператор «=». --vityok 21:57, 16 грудня 2006 (UTC)
- left + (right - left)/2 - а це навіщо? Адже OCaml has a built-in library for arbitrary precision arithmetic ---- Ілля 22:26, 16 грудня 2006 (UTC)
ще - а якщо елементи списки не підтримують більше,менше? ---- Ілля 22:48, 16 грудня 2006 (UTC)

