Advertisement
allia

бинарный поиск по матрице

Nov 5th, 2020
1,828
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5.  
  6. int bin_poisk (int **result, int left, int right, int key, int index_str)
  7. {
  8.   int i = 0;
  9.   while (left < right)
  10.   {
  11.     i = (left + right) / 2;
  12.     if (result[index_str][i] < key)
  13.      left = i+1;
  14.     else right = i;
  15. }
  16.  
  17. if (result[index_str][right] == key)
  18.  
  19. return right;
  20. return -1;
  21. }
  22.  
  23. int* bin_poisk_1 (int **arr, int left, int right, int key, int razmer)
  24. {
  25.   int i = 0;
  26.   int index_stolb = -1;
  27.  
  28.   while (right > left && index_stolb == -1)
  29.   {
  30.     i = (left + right) / 2;
  31.     if (arr[i][razmer] < key )
  32.      {
  33.        left = i+1;
  34.        index_stolb = bin_poisk(arr, 0, razmer, key, i+1);
  35.      }
  36.     else
  37.     {
  38.       right = i;
  39.       index_stolb = bin_poisk(arr, 0, razmer, key, i);
  40.     }
  41. }
  42.  
  43. int *result = new int[2];
  44.  
  45. result[0] = i;
  46. result[1] = index_stolb;
  47.  
  48. return result;
  49. }
  50.  
  51. int main()
  52. {
  53.   int n, m, znach, shet = 0;
  54.   cin >> n >> m;
  55.   cin >> znach;
  56.  
  57.   int **arr = new int*[n];
  58.  
  59.    for (int i = 0; i < n; i++)
  60.       arr[i] = new int[m];
  61.    
  62.    for (int i = 0; i < n; i++)
  63.      for (int j = 0; j < m; j++)
  64.          cin >> arr[i][j];
  65.  
  66.   int *index = new int[2];
  67.  
  68.   index = bin_poisk_1(arr, 0, m-1, znach, m-1);
  69.  
  70. cout << index[0]+1  << " " << index[1]+1;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement