Akademia Gimnazjalna 2016/2017 - semestr letni

Zajęcia 28 marca

Omówione zagadnienia

• Wyszukiwanie binarne - algorytm oraz omówienie problemów implementacyjnych.
• Wyszukiwanie binarne po wyniku.
• Pary w języku C++.

Materiały

• Artykuł Marcina Oczeretki nt. wyszukiwania binarnego: https://informatyka.wroc.pl/node/409
• Przykład - funkcja, który sprawdza, czy wśród a[1],..., a[n] znajduje się liczba q.
  

  bool binary_search(int q){
      int p=0, k=n+1;
      while(p+1 < k){
          int sr = (p+k)/2;
          if(a[sr] < q)
              p = sr;
          else
              k = sr;
      }
  
      return a[k] == q;
  }