a+b+c=0 dla posortowanej tablicy

Czesc mam do napisania program, który sprawdza czy w posortowaniej tablicy sa takie liczby które spełniaja warunek a+b+c=0, (liczby nie musza byc rowne)napisalem taki program, ale musi byc on szybszy;/ moze ktos ma pomysl na algorytm ja zrobilem to iterujac po kazdej z liczb po kolei tzn. a szukam na poczatku, b+1, c od konca. Tu kod:

 
  for(i=0;i<size;i++){
  a=array[i];
    for(j=1;j<size-2;j++){
    b=array[j];
      for(k=size-1;k>0;k--){
        c=array[k];
        abc=a+a+c;
        if(!abc){printf("TAK %d %d %d\n",i,i,k);break;}
        abc=a+c+c;
        if(!abc){printf("TAK %d %d %d\n",i,k,k);break;}
        abc=a+b+c;
        if(!abc){printf("TAK %d %d %d\n",i,j,k);break;}
      }
      if(!abc)break;
    }
    if(!abc)break;
  }

Skoro tablica jest posortowana, to a i b jak do tej pory, ale C szukaj przez http://www.algorytm.org/dla-poczatkujacych/szukanie-polowkowe-binarne.html s. Dzięki temu znacznie przyśpieszy. Co więcej fakt że tablica od początku jest posortowana wskazuje że bez tego raczej "nie przejdzie"

Rozumiem, znam algorytm ale w zadaniu nie jest powiedziane, ze takie dzialanie musi byc, nie potrafie jeszcze obliczac tej zlozonosci i niewiem czy oplaca sie tak kombinowac dla przypadku w ktorym nie ma tej liczby?

Złożoność to logarytm o podstawie 2 z ilości liczb. Czyli gdyby tych liczb było milion, po 20 (to skrajnie pesymistyczny przypadek, prawdopodobnie dużo szybciej) sprawdzeniach wiedział byś czy jest c . A jakiej liczby szuka żeby wynik wyszedł zero policzysz sobie bez trudu.

Generalnie korzystaj z tego szukania zawsze gdy masz posortowaną tablicę, a jak nie masz to upewnij się że jej posortowanie nie będzie szybsze od twojego szukania (prawdopodobnie będzie).

@Laik93 teraz masz 3 pełne pętle czyli O(n³). Wymiana jednej z nich na szukanie połówkowe to zmiana jednego O(n) na O(logn) więc już "tylko" O(n²logn). Pytasz czy się opłaca? Dla miliona elementów z jednej strony masz O(n) czyli milion liczb do sprawdzenia, z drugiej masz O(log2(n)) czyli ratem 20 elementów do sprawdzenia czyli teoretycznie jesteś szybszy 50 000 razy. Dla miliarda z jednej strony masz miliard a z drugiej masz 30 wiec jesteś szybszy 300 000 000 razy ;]