Обговорення:Двійковий пошук

Матеріал з Вікіпедії — вільної енциклопедії.

На скільки я зрозумів — алогоритм є рекурсивним, і краще б його приклад виглядав у рекурсивній формі. Чи не так? --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)

  1. Твоє питання я розумію так, що ти не знав раніше як працює двійковий пошук? Невже?
  2. Вірна твоя реалізація чи містить помилку можна сказати лише знаючи представлення масивів та логіку 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)