Advertisement
O_Egor

Поиск (бинарный/линейный)

Sep 29th, 2022
642
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <time.h>
  5.  
  6. using namespace std;
  7.  
  8. bool binarySearch(vector <int> v, int a) //Функция бинарного поиска
  9. {
  10.     int kd(0), l(0), r(v.size() - 1); //kd - счётчик действий, l - левая граница поиска, r - правая
  11.     sort(v.begin(), v.end()); //Сортируем массив, так как бинарный поиск работает только в отсортированной последовательности
  12.                               //Здесь мы не считаем кол-во действий, но про них стоит сказать, ведь сортировка занимает O(nlogn) действий,
  13.                               //где n - размер массива. sort() работает на основе быстрой сортировки
  14.  
  15.     while (l < r)//стандартный алгоритм бинарного поиска
  16.     {
  17.         kd++;   // каждый раз прибавляем количество действий, так как на каждой итерации производим одно сравнение
  18.         int m = (l + r) / 2; //каждый раз выбираем новую середину
  19.         if (v[m] == a) // если середина равна искомому числу, говорим, что число найдено
  20.         {
  21.             cout << "Kol-vo deistvii: " << kd << '\n';
  22.             return 1;
  23.         }
  24.         if (v[m] > a)// если середина больше искомого числа, значит, что наше число левее середины, поэтому правую границу поиска смещаем влево
  25.         {
  26.             r = m;
  27.         }
  28.         else// иначе, искомое число правее середины, тогда смещаем левую гарницу вправо
  29.         {
  30.             l = m + 1;
  31.         }
  32.     }
  33.     cout << "Kol-vo deistvii: " << kd << '\n';
  34.     return 0;
  35. }
  36.  
  37. bool linearSearch(vector <int> v, int a) //Функция линейного поиска
  38. {
  39.     int kd(0);//тоже самое, что и в бинарном поиске
  40.     bool f(0);//флаг, для того, чтобы знать, нашли мы число или нет
  41.     //линейный поиск может работать на неотсортированной последоваетльности, поэтому мы ничего не сортируем
  42.  
  43.     for (int i = 0; i < v.size(); ++i)
  44.     {
  45.         kd++;//считаем кол-во сравений
  46.         if (v[i] == a)//если нашли число, то "поднимаем" флаг и выхожим из цикла
  47.         {
  48.             f = 1;
  49.             break;
  50.         }
  51.     }
  52.     cout << "Kol-vo deistvii: " << kd << '\n';
  53.     return f;
  54. }
  55.  
  56. int main()
  57. {
  58.     int sz;//размер массива, который вводим ниже
  59.     cout << "Input size of array: ";
  60.     cin >> sz;
  61.    
  62.     vector <int> v(sz);//сам массив
  63.    
  64.     srand(time(NULL));//это для того, чтобы рандомно заполнять массив разными числами
  65.    
  66.     for (int i = 0; i < sz; ++i)
  67.     {
  68.         v[i] = rand() % 100;//вот тут происходит заполнение, возможные числа от 0 до 100, вроде...
  69.         cout << v[i] << ' ';
  70.     }
  71.  
  72.     int a, type;//а - число, которое мы ищем, type - тип поиска, который мы выибраем ниже
  73.     cout << "\nInput number, you want to find: ";
  74.     cin >> a;
  75.  
  76.     cout << "Choose algorithm of search:\n1) Linear search\n2) Binary search\n3) Stop\n"; //здесь выбираем
  77.     while (true)//цикл будет работать вчено, пока не будет введена "3", это чтобы постоянно не перезапускать программу
  78.     {
  79.         cin >> type;//вернее здесь выбираем))
  80.         if (type == 1)
  81.         {
  82.             if (linearSearch(v, a))//вызываем функцию линейного поиска, которая возвращает либо true, либо false
  83.             {
  84.                 cout << a << " is in the sequence\n";//если true, то число есть в последовательности
  85.             }
  86.             else
  87.             {
  88.                 cout << a << " is not in the sequence\n";//если false - нет в последовательности
  89.             }
  90.         }
  91.         else if (type == 2)
  92.         {
  93.             if(binarySearch(v, a))//всё тоже саме, что и выше
  94.             {
  95.                 cout << a << " is in the sequence\n";
  96.             }
  97.             else
  98.             {
  99.                 cout << a << " is not in the sequence\n";
  100.             }
  101.         }
  102.         else if (type == 3)// это для того, чтобы закончить программу
  103.         {  
  104.             cout << "End of programm\n";
  105.             break;
  106.         }
  107.         else
  108.             cout << "Incorrect type of search, try again!\n";//это для того, если ввели неправильный тип (не 1, 2 или 3)
  109.         cout << "Choose algorithm of search (if needed):\n1) Linear search\n2) Binary search\n3) Stop\n";
  110.     }
  111.    
  112.  
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement