Algorytmy

Przeszukiwanie posortowanej tablicy

  • 3 komentarze
  • 892 odsłony
  • Oceń ten tekst jako pierwszy
Czesto istnieje potrzeba stwierdzenia na ktorej pozycji w posortowanej tablicy  T znajduje sie element o danej wartosci x lub stwierdzenia ze w tablicy T nie ma elementu o wartosci x.

Problem ten mozna rozwiazac przeszukiwaniem binarnym.

Sluzy do tego funkcja find :

int find(int p, int k, int x){
  int s=(p+k)>>1;
    if(T[s]==x)return s;
    else if(p==k)return -1;
    else if(T[s]<x) return find(s+1,k,x);
    else return find(p,s-1,x);
} 


Metoda ta dziala w czasie pesymistycznym O(log n) gdzie n to ilosc elementow w tablicy T. Przykladowy program uzywajacy funkcji find:

#include "stdio.h"
int T[1000];
 
int find(int p, int k, int x){
(...)
}
 
main(){
  int n,x;
  scanf("%d",&n);
    for(int i=0;i<n;;++i) scanf("%d",&T[i]);
  scanf("%d",&x);
  printf("%d\n", find(0,n-1,x));
  return 0;
}


Powyzszy program wczytuje tablice T oraz szukana wartosc elementu (x) i wypisuje pozycje w tablicy T elementu o wartosci x. Gdy takowego elementu nie ma to program wypisuje -1.

3 komentarze

Xitami 2006-10-18 12:33

----------------------------------------------------------------------------------------------------------------------
Rekurencyjnie?!?! To błąd w sztuce!!!

function szukam(s:tslowo):longint;
var p,c,k:longint;
begin
  p:=1; k:=n;
  repeat
    c:=(p+k) div 2;
    if s<dd[c] then k:=c-1
    else if dd[c]<s then p:=c+1
    else p:=k+1
  until p>k;
  if dd[c]=s then result:=c else result:=0;
end;

-----------------------------------------------------------------------------------------------------------[ Xitami ]-

brodny 2005-12-13 22:58

A kod nieładny ;P

AklimX 2005-09-03 00:15

nie mogę uwierzyć, że jeszcze tego nie było...

[edit] no i obszerne jak na artykuł [glowa]