C++ - Wyszukiwanie liczb w tabeli

W tym poście chciałbym opisać sposób wyszukiwania liczb w tabeli posortowanej. Algorytm wyszukiwania będzie się opierał na metodzie zwanej przeszukiwaniem binarnym.

Program

W pierwszej kolejności należy się zająć częścią programu odpowiedzialną za sortowanie liczb. Ja wykorzystałem algorytm sortowania bąbelkowego. Jest to jedna z prostszych metod sortowania. Działa ona dosyć dobrze na małych zbiorach, przy większych zbiorach raczej sobie nie poradzi za dobrze.

Dane w czasie sortowania są przemieszczają się w prawą stronę, czyli ku ostatniemu elementowi w tablicy. Ich miejsce zajmują elementy o mniejszej wartości. Algorytm jest powtarzany dla każdej z liczb z pominięciem licz które zostały już posortowane. Całość jest powtarzana aż do momentu ich poprawnego ułożenia.

1. void sortowanie(int tab[],int n)
2. {
3.   for(int i=0;i<n;i++)
4.   {
5.     for(int j=1;j<n-i;j++)
6.     {
7.         if(tab[j-1]>tab[j])
8.         {
9.           //Zamiana elementow miejscami
10.           swap(tab[j-1], tab[j]);
11.         }
12.     }
13.   }
14. }

Poniżej wklejam pełny kod programu wraz z komentarzem:

1. #include <iostream>
2. #include<cstdlib>
4. #define TabEle 16
6. using namespace std;
8. int wyszukaj(int  tabl[], int x, int left, int right);
9. void sortowanie(int tab[],int n);
11. int main()
12. {
13.      //Deklaracja tablicy
14.      int tabl[TabEle]={2,1,15,34,20,29,45,32,18,39,21,71,43,47,11,9};
15.      const int Szuk1 = 45;
16.      const int Szuk2 = 38;
17.      //Wypisanie i wyświetlenie wyszukanych cyfr
18.      for(int i=0; i<TabEle; i++)
19.      {
20.        cout << tabl[i] << "  ";
21.      }
22.      //Przejscie do nowej linii
23.      cout << endl;
25.      sortowanie(tabl, TabEle);
27.      for(int i=0; i<TabEle; i++)
28.      {
29.        cout << tabl[i] << "  ";
30.      }
31.      cout << endl;
33.      //Przeszukiwanie tablicy, wyszukanie miejsc na jakiej znajduja sie elementy
34.      //Jesli elementu nie ma w tablicy to wyswietli wartosc -1
36.      cout << "Wyszukaj liczbe "<< Szuk1 << ", jej pozycja to: " << wyszukaj(tabl,Szuk1, 0, 16)<<endl;
38.      if(wyszukaj(tabl, 3,0,16)>-1)
39.      {
40.          cout << "Wyszukaj liczbe " << Szuk2 << ", jej pozycja to: " << wyszukaj(tabl, Szuk2, 0, 16);
41.      }
42.      else
43.      {
44.          cout << "Nie znaleziono szukanej liczby" << endl;
45.      }
46.      return 0;
47. }
49. int wyszukaj(int  tabl[], int x, int left, int right)
50. {
51.      if(left>right)
52.      {
53.          //Jesli nie znajdzie elementu, wtedy zwrocona bedzie wartosc -1
54.          return -1;
55.      }
56.      else
57.      {
58.          //Przypisanie zmiennej srodek wartosci rownej polowie liczby elementow
59.          int srodek=(left+right)/2;
61.          //Sprawdzenie czy wartosc srodkowa jest szukanym elementem
62.          if(tabl[srodek]==x)
63.          {
64.            //Jesli znajdzie element wtedy zwraca jego pozycje
65.            return srodek;
66.          }
67.          else
68.          {
69.                 //Sprawdzenie wartosci elementu
70.                 if(x<tabl[srodek])
71.                 {
72.                     //Wejscie do funkcji wyszukiwania w strone nizszej pozycji
73.                     return wyszukaj(tabl,x,left,srodek-1);
74.                 }
75.                 else
76.                 {
77.                     //Wyjscie do funkcji wyszukiwania w strone wyzszej pozycji
78.                     return wyszukaj(tabl,x,srodek+1,right);
79.                 }
80.          }
81.     }
82. }
84. void sortowanie(int tab[],int n)
85. {
86.   for(int i=0;i<n;i++)
87.   {
88.     for(int j=1;j<n-i;j++)
89.     {
90.         if(tab[j-1]>tab[j])
91.         {
92.           //Zamiana elementow miejscami
93.           swap(tab[j-1], tab[j]);
94.         }
95.     }
96.   }
97. }

W pierwszej kolejności deklarowana jest tablica elementów oraz zmienne. Następnie wyświetlana jest aktualna tablica liczb, która w kolejnych krokach jest sortowana. Funkcja wyszukiwania zadanej wartości przechodzi po kolejnych jej elementach do momentu odnalezienia zadanej wartości.