StoneHaos

5

Nov 28th, 2021
799
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int binarySearch(int *a, int n, int key) {
  9.     bool flag = false;
  10.     int l = 0; // левая граница
  11.     int r = n-1; // правая граница
  12.     int mid;
  13.     while ((l <= r) && (flag != true)) {
  14.         mid=(l + r)/2; //считываем срединный индекс отрезка [l,r]
  15.         if (a[mid] == key) flag = true; //проверяем ключ со серединным элементом
  16.         if (a[mid] > key) r = mid - 1; // проверяем, какую часть нужно отбросить
  17.         else l = mid + 1;
  18.     }
  19.     if (a[mid] == key)
  20.         return mid;
  21.     else
  22.         return -1;
  23. }
  24.  
  25. int main() {
  26.     srand(time(NULL));
  27.     int n;
  28.     cin >> n;
  29.     int *a = new int[n];
  30.     for (int i = 0; i < n; i++) a[i] = rand() % 50;
  31.     sort(a, a + n);
  32.     for (int i = 0; i < n; i++) cout << a[i] << " ";
  33.     cout << endl;
  34.     int key;
  35.     cin >> key;
  36.     cout << "index " << binarySearch(a, n, key) << endl;
  37.     delete [] a;
  38.     return 0;
  39. }
RAW Paste Data