Как использовать двоичный поиск с двумерным массивом?

Question

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

Вот код, который был записан в книге (некоторые из них):

package Test; 
import java.util.Scanner; 
public class TestMain { 
public static void main(String[]args){ 
    int[]numbers = {1,2,3,4,5}; 
    int numInput = getNumInput(); 
    int result = binarySearch(numbers,numInput); 
    if(result == -1){ 
     System.out.print("No Match Found!"); 
    }else{ 
     System.out.print("Match Found!"); 
    } 
} 

public static int getNumInput(){ 
    Scanner hold = new Scanner(System.in); 
    int num; 
    System.out.print("Enter number:"); 
    num = hold.nextInt(); 
    return num; 
} 

public static int binarySearch(int[]numbers,int numInput){ 
    int first = 0; 
    int middle; 
    int last = numbers.length - 1; 
    int position = -1; 
    boolean found = false; 
    while(!found && first < numbers.length){ 
     middle = (first + last)/2; 
     if(numbers[middle]==numInput){ 
      found = true; 
      position = middle; 
     }else if(numbers[middle]>numInput){ 
      last = middle - 1; 
     }else{ 
      first = middle + 1; 
     } 
    } 
    return position; 
} 
} 

А вот мой код пытается использовать два двумерный массив:

package Practice; 
import java.util.Scanner; 
public class Practice1Main { 

public static void main(String[]args){ 
    int[][]numbers = {{1,2},{3,4},{5,6}}; 
    int numInput = getNumInput(numbers); 
    int result = binarySearch(numbers,numInput); 
    if(result == -1){ 
     System.out.print("No Match Found!"); 
    }else{ 
     System.out.print("Match Found!"); 
    } 

} 

public static int getNumInput(int[][]numbers){ 
    Scanner hold = new Scanner(System.in); 
    int num; 
    System.out.print("Enter number:"); 
    num = hold.nextInt(); 
    return num; 
} 

public static int binarySearch(int[][]numbers,int numInput){ 
    int first = 0; 
    int middle; 
    int last = 2; 
    int position = -1; 
    boolean found = false; 

    while(!found && first < numbers.length){ 
     middle = (first + last)/2; 
     if(numbers[middle][first]==numInput){ 
      found = true; 
      position = middle; 
     }else if(numbers[middle][first]>numInput){ 
      last = middle - 1; 
     }else{ 
      first = middle + 1; 
     } 
    } 
    return position; 
} 
} 

Выход был способный искать от 1 до 3. Однако, когда вы вводите число 4, оно даст мне ошибку ArrayIndexOutOfBoundsException.

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

Answer 1

(Во-первых, я думаю, что вы выбрали довольно "неинтересный" проблему решить.)

Итак, как можно обобщить с 1-D 2-D (или п-D)? Вот пара идей.

1) Предположим, что у нас есть 2-D прямоугольный массив типа int[][]. Проще всего (мысленно) сопоставить этот массив с одномерной системой координат; например

• [0, 0] -> [0]
• [0, 1] -> [1]
• ...
• [0, N - 1] -> [N - 1]
• [1, 0] -> [N]
• [1, 1] -> [N + 1]
• ...
• [М - 1, N - 1] -> [N x M - 1]

и, конечно, координатное отображение идет и в другую сторону. Итак ... одним из подходов к решению двумерного бинарного поиска является вычисление индексов в соответствии с 1-D массивом и преобразование в 2-D координаты для поиска массива.

2) Двухмерный массив на самом деле представляет собой 1-мерный массив 1-мерных массивов. Таким образом, второй подход к решению - сначала выполнить одномерный двоичный поиск, чтобы найти массив, содержащий нужный вам номер, а затем выполнить второй одномерный поиск в найденном массиве. Обратите внимание, что вы можете выполнить начальный 1-D поиск, просто взглянув на первый элемент каждого 1-D подмассива.

Answer 2

Большая часть любой проблемы в области компьютерных наук позволяет разбить общую проблему на более мелкие разделы, которые вы знаете, как их решить. По этому вопросу вы спрашиваете, как выполнять двоичный поиск в двумерном массиве, но вы знаете только, как это сделать на одномерном массиве. Таким образом, вы должны думать об этой проблеме в два этапа - найти способ преобразования двумерного массива в одномерный, а затем выполнить двоичный поиск в этом преобразованном массиве.

Вы упомянули, что знаете, как выполнять двоичный поиск в одномерном массиве, поэтому я пропущу этот шаг.Давайте посмотрим на метод преобразования:

Похоже, вы используете Java, и я не удивлюсь, увидев, что Java имеет встроенную функцию, которая делает все это для вас. Предположим, что это не так. Мы знаем, что ваш массив чисел [] [] представляет собой матрицу 3 X 2. Это означает, что в матрице 6 элементов. Поэтому у нашего одномерного массива будет 6 предметов.

int[] new_array = new int[6]; 

Затем мы можем выполнить цикл для всех элементов вашего начального массива и заполнить их новыми.

int counter = 0; 
for(int j = 0; j < 3; j++) 
{ 
    for(int i = 0; i < 2; i++) 
    { 
     new_array[counter] = numbers[j][i]; 
     counter++; 
    } 
} 

И теперь у вас есть одномерный массив. Двоичный поиск отсюда, чтобы получить окончательный ответ.