Než pochopíme rozdíly mezi lineárním a binárním vyhledáváním, měli bychom nejprve samostatně znát lineární vyhledávání a binární vyhledávání.
Co je lineární vyhledávání?
Lineární vyhledávání je také známé jako sekvenční vyhledávání, které jednoduše prohledává každý prvek najednou. Předpokládejme, že chceme prohledat prvek v poli nebo seznamu; jednoduše vypočítáme jeho délku a neskočíme na žádnou položku.
Podívejme se na jednoduchý příklad.
Předpokládejme, že máme pole 10 prvků, jak je znázorněno na obrázku níže:
Výše uvedený obrázek ukazuje pole typu znaků s 10 hodnotami. Pokud chceme hledat „E“, pak vyhledávání začíná od 0čtprvek a skenuje každý prvek, dokud prvek, tj. 'E' není nalezen. Nemůžeme přímo skočit z 0čtprvek do 4čtprvek, tj. každý prvek je skenován jeden po druhém, dokud prvek není nalezen.
Složitost lineárního vyhledávání
Lineární vyhledávání prohledává každý prvek jeden po druhém, dokud prvek není nalezen. Pokud se počet prvků zvýší, zvýší se také počet prvků ke skenování. Můžeme říci, že čas potřebný k vyhledání prvků je úměrný počtu prvků . Nejhorší případ složitosti je tedy O(n)
Co je binární vyhledávání?
Binární vyhledávání je vyhledávání, při kterém se počítá prostřední prvek, aby se zjistilo, zda je menší nebo větší než prvek, který má být prohledán. Hlavní výhodou použití binárního vyhledávání je, že neprohledává každý prvek v seznamu. Místo skenování každého prvku provádí vyhledávání do poloviny seznamu. Binární vyhledávání tedy zabere prohledání prvku méně času ve srovnání s lineárním vyhledáváním.
Jeden předpoklad binárního vyhledávání je, že pole by mělo být v seřazeném pořadí, zatímco lineární vyhledávání funguje na seřazeném i netříděném poli. Binární vyhledávací algoritmus je založen na technice rozděl a panuj, což znamená, že pole rozděluje rekurzivně.
V binárním vyhledávání se používají tři případy:
Případ 1: data
Případ 2: data>a[mid] pak vpravo=střed-1
Případ 3: data = a[mid] // prvek byl nalezen
Ve výše uvedeném případě „ A ' je název pole, střední je index prvku vypočítaný rekurzivně, data je prvek, který se má hledat, vlevo, odjet označuje levý prvek pole a že jo označuje prvek, který se vyskytuje na pravé straně pole.
Pojďme pochopit fungování binárního vyhledávání na příkladu.
Předpokládejme, že máme pole o velikosti 10, které je indexováno od 0 do 9, jak je znázorněno na obrázku níže:
Chceme hledat 70 prvků z výše uvedeného pole.
Krok 1: Nejprve vypočítáme střední prvek pole. Uvažujeme dvě proměnné, tedy levou a pravou. Zpočátku vlevo = 0 a vpravo = 9, jak je znázorněno na obrázku níže:
Hodnotu prostředního prvku lze vypočítat takto:
Mid = 4 a a[mid] = 50. Prvek, který se má hledat, je 70, takže a[mid] se nerovná datům. Případ 2 je splněn, tj. data>a[mid].
Krok 2: Jako data>a[mid], takže hodnota left se zvýší o střední+1, tj. left=mid+1. Hodnota mid je 4, takže hodnota left bude 5. Nyní máme podpole, jak je znázorněno na obrázku níže:
Nyní se opět střední hodnota vypočítá pomocí výše uvedeného vzorce a hodnota střední hodnoty bude 7. Nyní lze střední hodnotu reprezentovat jako:
Na výše uvedeném obrázku můžeme pozorovat, že a[mid]>data, takže opět bude v dalším kroku vypočtena hodnota mid.
Krok 3: Jako [mid]>data je hodnota práva snížena o polovinu 1. Hodnota mid je 7, takže hodnota right bude 6. Pole může být reprezentováno jako:
Znovu se vypočítá hodnota mid. Hodnoty vlevo a vpravo jsou 5 a 6. Proto je hodnota mid 5. Nyní může být střed reprezentován v poli, jak je uvedeno níže:
Na obrázku výše můžeme pozorovat, že [uprostřed]
Krok 4: Jako [uprostřed] Nyní se hodnota mid vypočítá znovu pomocí vzorce, který jsme již probrali. Hodnoty vlevo a vpravo jsou 6 a 6, takže hodnota středu bude 6, jak je znázorněno na obrázku níže: Na výše uvedeném obrázku můžeme pozorovat, že a[mid]=data. Proto je hledání dokončeno a prvek je úspěšně nalezen. Níže jsou uvedeny rozdíly mezi lineárním a binárním vyhledáváním: Popis Lineární vyhledávání je vyhledávání, které najde prvek v seznamu postupným prohledáváním prvku, dokud není prvek nalezen v seznamu. Na druhou stranu, binární vyhledávání je vyhledávání, které najde prostřední prvek v seznamu rekurzivně, dokud se prostřední prvek neshoduje s hledaným prvkem. Práce obou vyhledávání Lineární vyhledávání zahájí vyhledávání od prvního prvku a prohledává jeden prvek po druhém, aniž by přecházelo na další prvek. Na druhou stranu binární vyhledávání rozdělí pole na polovinu výpočtem středního prvku pole. Implementace Lineární vyhledávání lze implementovat na libovolné lineární datové struktuře, jako je vektor, jednoduše propojený seznam, dvojitě propojený seznam. Naproti tomu binární vyhledávání může být implementováno na těchto datových strukturách s obousměrným průchodem, tj. průchodem vpřed a vzad. Složitost Lineární vyhledávání se používá snadno, nebo můžeme říci, že je méně složité, protože prvky pro lineární vyhledávání mohou být uspořádány v libovolném pořadí, zatímco v binárním vyhledávání musí být prvky uspořádány v určitém pořadí. Seřazené prvky Prvky pro lineární vyhledávání mohou být uspořádány v náhodném pořadí. Při lineárním vyhledávání není povinné, aby byly prvky uspořádány v seřazeném pořadí. Na druhou stranu při binárním vyhledávání musí být prvky uspořádány v seřazeném pořadí. Může být uspořádán ve vzestupném nebo sestupném pořadí a podle toho se změní algoritmus. Protože binární vyhledávání používá tříděné pole, je nutné vložit prvek na správné místo. Naproti tomu lineární vyhledávání nepotřebuje seřazené pole, takže nový prvek lze snadno vložit na konec pole. Přístup Lineární vyhledávání používá k nalezení prvku iterativní přístup, takže je také známé jako sekvenční přístup. Naproti tomu binární vyhledávání počítá prostřední prvek pole, takže používá přístup rozděl a panuj. Soubor dat Lineární vyhledávání není vhodné pro velký soubor dat. Pokud chceme prohledat prvek, který je posledním prvkem pole, začne lineární vyhledávání hledat od prvního prvku a pokračuje až k poslednímu prvku, takže čas potřebný k prohledání prvku by byl velký. Na druhou stranu je binární vyhledávání vhodné pro velký soubor dat, protože zabere méně času. Rychlost Pokud je soubor dat při lineárním vyhledávání velký, výpočetní náklady by byly vysoké a rychlost by se zpomalila. Pokud je soubor dat při binárním vyhledávání velký, výpočetní náklady by byly nižší ve srovnání s lineárním vyhledáváním a rychlost se zrychlí. Rozměry Lineární vyhledávání lze použít na jednorozměrném i vícerozměrném poli, zatímco binární vyhledávání lze implementovat pouze na jednorozměrném poli. Účinnost Lineární vyhledávání je méně efektivní, vezmeme-li v úvahu velké soubory dat. Binární vyhledávání je v případě velkých souborů dat efektivnější než lineární. Podívejme se na rozdíly v tabulkové podobě. 
Rozdíly mezi lineárním a binárním vyhledáváním
java je instanceof
Základ srovnání Lineární vyhledávání Binární vyhledávání Definice Lineární vyhledávání začne hledat od prvního prvku a porovnává každý prvek s hledaným prvkem, dokud prvek nenajde. Zjistí polohu hledaného prvku nalezením prostředního prvku pole. Seřazená data Při lineárním vyhledávání není nutné prvky řadit v seřazeném pořadí. Předpokladem pro binární vyhledávání je, že prvky musí být uspořádány v seřazeném pořadí. Implementace Lineární vyhledávání lze implementovat na jakoukoli lineární datovou strukturu, jako je pole, propojený seznam atd. Implementace binárního vyhledávání je omezená, protože může být implementována pouze na těch datových strukturách, které mají obousměrný průchod. Přístup Je založen na sekvenčním přístupu. Je založen na přístupu rozděl a panuj. Velikost Je vhodnější pro malé soubory dat. Je vhodnější pro velké soubory dat. Účinnost V případě velkých souborů dat je méně efektivní. Je to efektivnější v případě velkých souborů dat. Nejhorší scénář Při lineárním vyhledávání je nejhorší scénář pro nalezení prvku O(n). Při binárním vyhledávání je nejhorší scénář pro nalezení prvku O(log2n). Nejlepší scénář Při lineárním vyhledávání je nejlepším scénářem pro nalezení prvního prvku v seznamu O(1). Při binárním vyhledávání je nejlepším scénářem pro nalezení prvního prvku v seznamu O(1). Rozměrové pole Může být implementován na jednorozměrném i vícerozměrném poli. Lze jej implementovat pouze na vícerozměrném poli.