Bináris (bináris) keresés
Amikor a keresés néhány elemet kell elvégezni rendezett növekvő vagy csökkenő sorrendben, akkor az algoritmus primenѝm bináris (binary) keresést. A módszer egy stratégia a „oszd meg és szabály”, nevezetesen, egy adott szekvencia van osztva két egyenlő részre, és a keresést végzünk az egyik ilyen alkatrész, amelyet azután szintén két részre, és így tovább, amíg a kívánt elem jelenlétének detektálására vagy annak hiánya. Ezzel a művelettel, minden alkalommal csökkenti a keresési terület felére, csak akkor fogadható el azon a tényen alapul, hogy a előrendelt elemek sorozatát. Megtaláljuk a középső elem (ehhez, ismerve a tömb elemeinek számát nem lesz nehéz), és összehasonlítja a kívánt értéket, akkor biztos lehet benne, hogy azt mondják, ahol van egy kötelező eleme vonatkozásában a középső elem.
Továbbá feltételezzük, hogy a tömb elemei növekvő sorrendben vannak elrendezve, mivel nincs jelentős különbség a rendezésükhöz képest: növekvő vagy csökkenő sorrendben. A keresési zóna határait a bal és a jobb, a baloldali és a jobb oldali elemek között is jelöljük.
Az algoritmus előrehaladása, szakaszokra osztva, a következő:
- keresési zóna (az első lépésben az egész tömb) két egyenlő részre osztható, közép (közép) elemének meghatározásával;
- az átlagos elemet összehasonlítjuk a szükséges (kulcs) értékkel, ennek az összehasonlításnak az eredménye három eset egyike:
- kulcs
- kulcs> közép. A keresési terület bal szélső része a középső elem mellett található (bal ← közép + 1);
- kulcs = közép. Az átlag és a szükséges elemek értékei azonosak, ezért az elem megtalálható, az algoritmus munkája befejeződött.
- kulcs
- ha nincs egyetlen elem sem a hitelesítéshez, akkor az algoritmus megszűnik, ellenkező esetben az 1. lépésre való áttérés végrehajtásra kerül.
Az alábbi táblázat egy konkrét egész számrendet és egy bináris keresési algoritmust lépésről-lépésre mutat be elemei számára. Helytakarékosság céljából a táblázatban a bal, jobb és középső helyeket a, b és c helyettesítik.
Van egy sorozata egész számok sorrendjében rendezi, és a kulcs - 16. Kezdetben, a számát határoló elemek olyan elemek számokkal 1 és 9, és az értékeket az 1. és 81. Számítsuk átlagos sejtszám, amely általában használ általános képletű (jobb + bal) / 2, vagy a bal + (jobb-bal) / 2 (a továbbiakban, a második képlet, mint a legellenállóbb túlcsordul) fogják használni a programokban. Miután az összehasonlítás, hogy a kívánt elem kisebb, mint az átlagos, és ezért a következő keresési végezzük a bal oldali részén a szekvencia. Az algoritmust továbbra is hasonló módon végezzük, amíg a kívánt elem 4. lépése nem található meg.
Érdemes megjegyezni, hogy ez sokkal kevesebb idő alatt, mint ha használják a lineáris keresés, de ellentétben a lineáris bináris keresés csak akkor működik, tömbök, amelynek elemeit rendezett, ami kétségtelenül ad neki egy negatív jellegét.
C ++ programkód:
#include "stdafx.h"
#include
névtér std;
const int N = 10;
bináris keresés
int BinarySearch # 40; int A # 91; # 93;. int kulcsot # 41;
# 123;
int bal = 0. jobb = N, közepes;
míg # 40; balra <= right )
# 123;
közép = bal + # 40; jobb - bal # 41; / 2;
ha # 40; kulcs egyébként, ha # 40; kulcs> A # 91; középső # 93; # 41; bal = közép + 1;
egyébként vissza a középső;
# 125;
visszatérés - 1;
# 125;
// fő funkció
void main # 40; # 41;
# 123;
setlocale # 40; LC_ALL, "Rus" # 41; ;
int i, kulcs;
int A # 91; N # 93; ;
cout <<"Искомый элемент> "; cin >> gomb; // írja be a kulcsot
cout <<"Исходный массив: " ;
mert # 40; i = 0; én
egyébként cout <<" \n Номер элемента: " <
# 125;
A Pascal program kódja:
BinSearch program;
használja a crt;
const N = 10;
típus Arr = tömb # 91; 1. N # 93; egész szám;
var közép. maradt. jobbra. gombot. i. integer;
A. Arr.
funkció BinarySearch # 40; A. Arr. gombot. egész szám # 41;. integer;
kezdődik
balra: = 1; jobbra: = N;
a bal oldalon<= right do
kezdődik
közép: = bal + # 40; jobb - bal # 41; div 2;
ha # 40; kulcs egyébként, ha # 40; kulcs> A # 91; középső # 93; # 41; majd balra: = közép + 1
else start BinarySearch: = mid; exit; végén;
végén;
BinarySearch: = - 1;
végén;
kezdődik
ír # 40; 'Keresés elem>' # 41; ; olvas # 40; kulcs # 41; ;
ír # 40; "Forrás tömb:" # 41; ;
i: = 1-től N-ig
kezdődik A # 91; én # 93; : = N * i; ír # 40; A # 91; én # 93;. „” # 41; ; végén;
writeln;
ha # 40; BinarySearch # 40; A. kulcs # 41; = - 1 # 41; akkor írj # 40; "Elem nem található" # 41;
más írni # 40; "Elem száma:". BinarySearch # 40; A. kulcs # 41; # 41; ;
végén.
A programban lehetőség van tömbellenőrzésre a benne lévő elemek jelenlétére, de mivel ez megtörtént, a felhasználótól függetlenül, szigorúan meghatározott számú állandó értékkel, ez nem szükséges.
Abban az esetben, ha a középérték első értéke megegyezik a kulccsal, akkor az algoritmus az O (1) legjobb idejéig teljesül. Az átlagos és legrosszabb esetben az algoritmus futási ideje O (logn), ami sokkal gyorsabb, mint a lineáris keresés, és lineáris időt igényel.