Typickou operací nad množinou je testování, zda obsahuje konkrétní prvek. Tato operace se jednak využívá při vkládání prvku do množiny, jednak bude často volána uživatelem. Její časová složitost je tedy kritická a měli bychom najít lepší řešení, než lineární vyhledávání, které jsme použili v implementaci třídy ArrayList. Možným vylepšením je udržovat seznam hodnot seřazený a pro testování přítomnosti prvku v tomto seznamu použít binárního vyhledávání.
Binární vyhledávání spočívá v rozdělení množiny prvků, kterou prohledáváme, na dvě části, a to takovým způsobem, že všechny hodnoty v levé části budou menší než hodnoty v pravé části. Podle hodnoty hledaného klíče pak rozhodneme, zda budeme dále hledat v levé nebo pravé části, a celý postup opakujeme dělením vybrané části až do okamžiku, kdy získáme hledaný prvek nebo prázdnou množinu klíčů. Je to vlastně zobecněná metoda půlení intervalu, kterou jistě znáte z numerické matematiky.
Složitost takového vyhledávání je logaritmická v případě, že dělení bude probíhat vždy na dvě stejně velké části. To znamená, že s každým zdvojnásobením počtu prohledávaných položek se čas nutný pro vyhledání prvku zvětší v nejhorším případě o konstantu.
Zajistíme-li uspořádání seznamu hodnot podle velikosti, můžeme využít variantu binárního vyhledávání nad seřazeným seznamem. To spočívá v neustálém půlení intervalu indexů, přičemž jako počáteční interval vezmeme rozsah všech indexů v seznamu. V každém kroku vybereme prostřední prvek a podle hodnoty jeho klíče zjistíme, zda se hledaná hodnota nachází v levé nebo pravé polovině. S vybranou polovinou indexů pak postup opakujeme, až se dostaneme k hledanému prvku nebo až se velikost intervalu zmenší na nulu a zjistíme, že prvek v seznamu není. V tomto případě máme vždy zajištěno, že dělení proběhne na dvě poloviny, takže časová složitost binárního vyhledávání nad seřazeným seznamem je vždy logaritmická. Jinou možností, jak realizovat binární vyhledávání, je použití seřazeného vyhledávacího stromu, kde tato podmínka již není automaticky splněna, ale k tomu se dostaneme později.
Na rozdíl od lineárního vyhledávání, kde jsme vystačili s metodou equals() pro porovnání prvků na rovnost, zde budeme ale potřebovat i uspořádání prvků a k tomu jazyk Java žádnou standardní metodu objektu nedefinuje. Napadá vás nějaké řešení?
Využijeme podobně jako v případě rozhraní Command triku se zapouzdřením operace do rozhraní a předání objektu, který toto rozhraní implementuje. Porovnatelnost objektů tedy můžeme zavést tak, že vytvoříme rozhraní Comparable obsahující metodu compareTo() pro porovnání a budeme vyžadovat, aby porovnávané objekty toto rozhraní implementovaly:
interface Comparable { int compareTo(Object o); }
Volání o1.compareTo(o2) vrátí zápornou hodnotu, pokud je o1 menší než o2, nulovou hodnotu, pokud se objekty rovnají, a kladnou hodnotu, je-li o1 větší než o2. Metoda compareTo() by měla být konzistentní s metodou equals() v tom smyslu, že compareTo() vrátí nulu právě tehdy, jestliže equals() vrátí true.
V následujícím příkladu si implementaci binárního vyhledávání s využitím rozhraní Comparable ukážeme prakticky.
Někdy se ovšem můžeme dostat do situace, kdy pracujeme s již definovanými třídami a nemůžeme si dovolit jejich definice rozšířit tak, aby přímo implementovaly rozhraní Comparable. V tom případě máme jinou možnost - můžeme definovat samostatnou třídu implementující následující rozhraní Comparator a její instanci použít pro porovnávání prvků množiny:
interface Comparator { int compare(Object o1, Object o2); }
Metoda compare() tohoto rozhraní zajistí porovnání dvou objektů stejně jako metoda compareTo() rozhraní Comparable; vrátí tedy zápornou, nulovou nebo kladnou hodnotu podle toho, zda je objekt o1 menší, roven nebo větší než o2.
Abychom pro tento přístup rozšířili implementaci třídy OrderedArraySet, stačí doplnit další konstruktor, jehož dalším parametrem bude Comparator, a upravit tělo metody search() tak, aby komparátor použila:
class OrderedArraySet implements Set { . . . public OrderedArraySet(int capacity, Comparator comparator) { list = new ArrayList(capacity); this.comparator = comparator; } private int search(Object elem) { int min = 0; int max = list.size() - 1; while( min <= max ) { int i = (min + max) / 2; Object obj = list.get(i); int compare; if( comparator == null ) compare = ((Comparable)elem).compareTo(obj); else compare = comparator.compare(elem, obj); if( compare < 0 ) max = i - 1; else if( compare > 0 ) min = i + 1; else return i; } return -1-min; } . . . protected Comparator comparator; }
Poznamenejme, že nastavení instanční proměnné comparator na hodnotu null je zajištěno definicí jazyka Java (na rozdíl od lokálních proměnných, které musíme vždy inicializovat).