Bisekcija

Iz MaFiRaWiki

Glej tudi članek bisekcija (iskanje ničle), ki opisuje numerični postopek za iskanje ničle funkcije.

Bisekcija je algoritem za iskanje podatka v urejeni tabeli.

Denimo, da iščemo mesto, na katerem se pojavi podatek x v urejeni tabeli

a_0, a_1, \ldots, a_{n-1}.

Ker na začetku ne vemo, kje v tabeli bi lahko bil x, je začetno iskalno območje celotna tabela a_0, \ldots, a_{n-1}. Nato v vsakem koraku prepolovimo (od tod ime bisekcija) trenutno iskalno območje a_i, \ldots, a_j tako, da primerjamo x s srednjim elementom območja ak, kjer je k = (i + j) / 2:

  • če je x < ak nadaljujemo iskanje na območju a_i, \ldots, a_{k-1},
  • če je x = ak smo našli x in vrnemo rezultat k,
  • če je x > ak nadaljujemo iskanje na območju a_{k+1}, \ldots, a_i.

Postopek se ustavi, ko najdemo podatek ali postane širina območja ji manjša od 1 (v tem primeru podatka ni v tabeli).

Časovna zahtevnost bisekcije je O(log(n)).

Implementacija

Primer

Imamo urejeno tabelo dvanajstih elementov, n = 12 in iščemo število x = 7.

Koraki:

  1. i = 0,j = 11,k = (0 + 11) / 2 = 5,a5 = 17 > 7, iščemo v prvi polovici iskalnega območja
  2. i = 0,j = 4,k = (0 + 4) / 2 = 2,a2 = 4 < 7 iščemo v drugi polovici iskalnega območja
  3. i = 3,j = 4,s = (3 + 4) / 2 = 3,a3 = 7 = 7 vrnemo rezultat 3.
Osebna orodja