Poszukiwanie wyjątkowego elementu zbioru

[homer_3009]

Witam, to mój pierwszy post na forum, szczerze mówiąc nie mam zbyt dużego pojęcia o matematyce, ale
męczy mnie ostatnio pewien problem teoretyczny - mam nadzieję, że z grubsza pasuje do tego działu

Problem wygląda tak:

Mamy zbiór n obiektów. Wśród tych obiektów jest jeden, który posiada jakąś unikalną właściwość - naszym zadaniem jest określenie który z obiektów posiada tą właściwość. Poszukiwany obiekt możemy wykryć poprzez przeprowadzenie dowolnej liczby tzw. testów. Jeden test możemy przeprowadzić na dowolnym podzbiorze obiektów. Wynikiem testu jest informacja, czy w testowanej grupie jest poszukiwany obiekt czy nie.

Czyli przykładowo jeśli przetestujemy cały zbiór na raz, to otrzymamy informację że poszukiwany obiekt jest wśród nich. Jeśli podzielimy zbiór na dwie części i dla każdej przeprowadzimy jeden test, to otrzymamy informację, w której z tych części jest obiekt etc.

Teraz pytanie: Jaka jest strategia pozwalająca wykryć poszukiwany obiekt w jak najmniejszej liczbie testów. I ewentualnie drugie pytanie - jak zmieni się strategia, jeśli w zbiorze będzie więcej niż jeden poszukiwany obiekt? Czy da się to opisać jakimś uniwersalnym wzorem?

[Lider Artur]

dzieląc na połowy obszar poszukiwania chyba jest najefektywniej

[Crizz]

Dodam tylko, że można to łatwo uzasadnić: przedstawiamy proces poszukiwania elementu wsród \(\displaystyle{ n}\)- elementowego zbioru w postaci drzewa decyzyjnego. Będzie to oczywiście drzewo binarne (szczególny element jest albo w przetestowanej, albo w nieprzetestowanej części). Oczekujemy \(\displaystyle{ n}\) możliwych wyników (pierwszy element, jest szczególny, drugi element jest szczególny, ...,\(\displaystyle{ n}\) - ty element jest szczególny), które będą stanowić liście drzewa.

Niech \(\displaystyle{ h}\) będzie wysokością tego drzewa. Z jednej strony, \(\displaystyle{ h \ge \lceil \log _{2}n\rceil}\) (taką co najmniej wysokość musi mieć drzewo binarne o \(\displaystyle{ n}\) liściach). Z drugiej strony, stosując właśnie strategię dzielenia na pół, otrzymamy (w najgorszym przypadku) pełne drzewo binarne o wysokości \(\displaystyle{ h = \lceil \log _{2}n\rceil}\).

[homer_3009]

Nieźle - dziękuję bardzo