Блог

В течение последних нескольких дней я пытался найти способ эффективного двоичного поиска такого массива и заставить его работать с любым заданным 2d-массивом такого рода.

Инструкции: В этом вопросе вы будете ссылаться на квадратичные двумерные массивы, то есть количество строк и столбцов равно числу строк и столбцов, равному n. определение разделения на четыре четверти размера n/2 следующим образом:

Учитывая такой тип массива, меня попросили выполнить поиск элемента с логарифмической временной сложностью, и если он был найден, я должен распечатать строку и столбец элемента в массиве.

У кого-нибудь есть решение для этого? Полное решение было бы потрясающим, но любой ответ будет оценен по достоинству.

Я поделюсь фрагментом кода, который очень запутан, но это то, к чему я пришел до сих пор, и он работает для большинства элементов массива, что недостаточно хорошо, так как это означает, что вся логика неверна.

 int[][] mat = {  {1, 2, 3, 4, 17, 18, 19, 20},  {8, 7, 6, 5, 24, 23, 22, 21},  {12, 11, 10, 9, 28, 27, 26, 25},  {16, 15, 14, 13, 32, 31, 30, 29},  {49, 50, 51, 52, 33, 34, 35, 36},  {56, 55, 54, 53, 40, 39, 38, 37},  {60, 59, 58, 57, 45, 46, 41, 42},  {64, 63, 62, 61, 48, 47, 44, 43}}; public static boolean search(int[][] mat, int num) {  int n = mat.length;  int i = 0;  int j = 0;  int[] indic = {-1, -1};  if (num gt; mat[n - 1][0] || num lt; mat[0][0]) {  return false;  }  while (n gt; 1) {  int minS1 = mat[i][j];  int maxS1 = mat[(n / 2) - 1   i][j];  int minS2 = mat[i][(n / 2)   j];  int maxS2 = mat[(n / 2) - 1   i][(n / 2)   j];  int minS3 = mat[(n / 2)   i][(n / 2)   j];  int maxS3 = mat[(n - 1)   i][(n / 2)   j];   int minS4 = mat[(n / 2)   i][j];  int maxS4 = mat[(n - 1)   i][j];  checkSquare(num, n, indic, i, j, minS1, minS2, minS3, minS4, maxS1, maxS2, maxS3, maxS4);  if (indic[0] != -1 amp;amp; indic[1] != -1) {  System.out.println("num="   num);  System.out.println("row="   indic[0]);  System.out.println("col="   indic[1]);  return true;  }  boolean x = false;  if (num gt; maxS2) {  if (num gt; maxS3) {  i  = n / 2;  } else {  if (n lt;= mat.length / 2 amp;amp; i lt;= (n / 2)) {  x = true;  i  = 1;  j  = 1;  } else {  if (i gt;= n / 2 amp;amp; j lt; n / 2 amp;amp; ((i lt; n) amp;amp; (j lt; n))) {  i  = 1;  j  = 1;  } else {   System.out.println(minS1);  System.out.println(minS2);  System.out.println(minS3);  i  = 1;  j  = 1;  }  }  }  } else {  if (num gt; maxS1) {  j  = n / 2;  } else {   if (num gt; minS2) {  if (j gt; (mat.length / 2))  j = 0;  j  = 1;  x = true;  } else j  = 1;  }  }  if (num == mat[i][j]) {  System.out.println("num="   num);  System.out.println("row="   i);  System.out.println("col="   j);  return true;  }  if (!x)  n = (n / 2);  }  return false; }  

Я не думаю, что 2D-массив, который вы дали, является правильным в соответствии с предоставленной вами картинкой. Все значения в верхнем квадранте (пронумерованные по часам, начиная с верхнего левого угла) должны быть больше, чем все значения в нижнем квадранте. И это правило также применяется ко всем поддиапазонам до тех пор, пока не будет достигнут размер 1×1. Например:

Элемент 24 помещен в положение 2-1-3, что означает положение 3 в первом под-квадранте второго главного квадранта.

Аналогично, элемент 19 помещается в положение 2-2-1, поэтому после 2-1-3

Надеюсь, я правильно понял.

Редактировать:

Вот как бы я поступил. Я позволю тебе самому разобраться с недостающими частями. Во-первых, определите функцию, которая возвращает границы квадранта:

 int[][] getQuadrantBounds(int iMin, int iMax, int jMin, int jMax){...}  

Пусть эта функция возвращает значение int[4][4]. Он содержит iMin, iMax, jMin, jMax четыре квадранта для.

Затем проверьте, является ли наименьший элемент в третьем квадранте больше, меньше или равен num . Помните, что самый маленький элемент в любом квадранте всегда находится в [jMin][iMin] или [iMin][jMin] в зависимости от вашей реализации.

После этого вы узнаете, находится ли элемент в квадрантах 1,2 или 3,4. Повторите процесс, но адаптируйте его для двух секторов. Теперь вы знаете, в каком квадранте num находитесь.

Конечно, вы сделали все это за какое-то время, как:

 while(iMax - iMin gt; 0){   int[][] quadrants = getQuadrantBounds(iMin, iMax, jMin, jMax);  //TODO find first element in third quadrant  //TODO nested if statements  //TODO update iMin, iMax, jMin, jMax accordingly inside if statements }   

Повторяйте до тех пор, пока не будет найдено или пока условие while больше не будет задано.

Вероятно, есть много возможностей для улучшения, но это должно дать время выполнения O(log_2(n)).