Przeszukiwanie posortowanej tablicy

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.