Wyszukiwanie

Lekcja 20 z 23 w kursie C++ – Standardowa biblioteka szablonów w Coddy.

Wyszukiwanie to proces lokalizowania pozycji określonego elementu w sekwencji elementów.

Algorytm wyszukiwania to algorytm, który otrzymuje argument x i próbuje znaleźć element o wartości x w danym zbiorze wartości. Wyszukiwanie elementu o takiej wartości może się więc nie powieść, jeśli taki element nie istnieje.

Istnieje wiele technik i metod wyszukiwania, ale w C++ poznasz:

Wyszukiwanie liniowe
Wyszukiwanie binarne

Wyszukiwanie liniowe

Wyszukiwanie liniowe to najbardziej podstawowa technika wyszukiwania, którą łatwo zaimplementować w C++. Jak sama nazwa wskazuje, podczas wyszukiwania liniowego klucz, którego szukamy, jest kolejno porównywany z każdym elementem sekwencji danych, aż do jego znalezienia lub końca sekwencji.

Linear Search(sequence, key)
	for each item in sequence:
		if item == key
			return item's index

W rzeczywistym kodzie wyszukiwanie liniowe będzie wyglądać mniej więcej tak:

int linear_search(int array[], int n, int x)
{
	for(int i = 0; i < n; i++)
		if(array[i] == x)
			return i;
	return 0;
}

int main()
{
	int array[] = {1, 2, 3, 4, 5};
	int n = 5;
	int x = 3;
	
	cout << "The index of the element " << x << " is " << linear_search(array, n, x);

Output:
The index of the element 3 is 2

Jak widać w powyższym kodzie, funkcja wyszukiwania liniowego przechodzi przez sekwencję elementów, aż znajdzie dopasowanie. Jeśli go nie znajdzie, zwraca -1.

Wyszukiwanie binarne

Wyszukiwanie binarne to algorytm wyszukiwania pozycji elementu, ale tablica musi być posortowana.
Algorytm wyszukiwania binarnego wykorzystuje technikę „dziel i zwyciężaj”, aby wyszukać klucz. Lista elementów jest wielokrotnie dzielona na połowy, a elementu szuka się w tej połowie, która jest bliżej celu.

Załóżmy, że szukamy elementu x = 4

Ustawianie wskaźników w wyszukiwaniu binarnym

Środkowy element w wyszukiwaniu binarnym

Znajdowanie środkowego elementu w wyszukiwaniu binarnym

Tak będzie wyglądać kod wyszukiwania binarnego.

int binarySearch(int array[], int x, int left, int right) {
  
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      left = mid + 1;

    else
      right  = mid - 1;
  }

  return -1;
}

int main()
{
    int array[] = {1, 5, 8, 10, 20};
    int x = 10;
    int n = 5;
    int result = binarySearch(array, x, 0, n - 1);
    
    if(result == -1)
    	cout << "Not found.";
    else
    	cout << "The element is found at " << result;

Output:
The element is found at 3

Pamiętaj, czym jest wyszukiwanie, jaki jest jego cel i do czego go używaliśmy. Pamiętaj też, jak zaimplementować wyszukiwanie liniowe i binarne. Ćwicz zaawansowane techniki w C++, rozwiązując zadania.

Wyzwanie

Średni

Podano 10 liczb wejściowych. W następnym wierszu znajduje się liczba N. W trzecim wierszu znajduje się N liczb, które określają, pozycje których elementów należy wyświetlić na ekranie.

Dane wejściowe
10 20 30 40 50 60 70 80 90 100
3
20
50
80

Dane wyjściowe
1 4 7

Spróbuj swoich sił

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// Enter your code here

int main()
{
    // Enter your code here

    return 0;
}