Двоичный поиск в 2D-массиве 3

Question

Мне нужно найти число в 2D-массиве. Колонки сортируются (от наименьшего значения до самого большого).

Вот мой код:

const int SIZE = 4; 
const int NOT_FOUND = 1; 
int binarySearch(int mat[][SIZE], int &line , int num); 

void main() 
{ 
    int num, index, mat[SIZE][SIZE] = { 11,1,5,11, 
             11,6,7,2, 
             8,7,7,7, 
             0,12,9,10 }; 

    int line = sizeof(mat)/sizeof(mat[0][0]); 

    cout << "please type a number to search: " << endl; 
    cin >> num; 

    index = binarySearch(mat, line, num); 

    if (index == NOT_FOUND) { 
     cout << "The value: " << num << "doesn't exist in the array\n"; 
    } 
    else { 
     cout << "The value: " << num << " exists in line " << line+1 
     <<" and column: " << index+1 << endl; 
    } 
    system("pause"); 
} 


int binarySearch(int mat[][SIZE], int &line, int num) 
{ 
    for (int j = 0; j < SIZE; j++) 
    { 
     int low = 0; 
     int high = SIZE - 1; 
     int middle; 

     while (low <= high) 
     { 
      middle = (low + high)/2; 

      if (num == mat[middle][j]) 
      { 
       line = middle; 
       return j; 
      } 
      else if (num < mat[middle][j]) { 
       high = middle - 1; 
      { 
      else { 
       low = middle + 1; 
      } 
     } 
    } 
    return NOT_FOUND; 
} 

Программа не находит все числа в массиве. Что-то не работает.

В чем проблема?

Answer 1

Вашего binarySearch не проходит через все числа, он проверяет первый номер, так что в вашем случае , то он переходит к следующему номеру, но он пропускает весь ряд чисел (1, 5 , 11) и первое число во втором ряду, а затем переместится на следующее второе число, которое будет во второй строке.

Поскольку у вас есть Матрица числа она состоит из Ряды и Колонны, это означает, что вы должны создать две петли for(...), один раз для строки и один для столбцов, так что вы можете пройти через все числа в ваш 2D-массив.

Я рекомендую установить Точка останова на функции binarySearch и, пройдя через это, это поможет вам.

Answer 2

Несколько вещей, которые я вижу неправильно в вашем коде ::

1) Оказывается, что вы подаете бинарный поиск в каждом столбце в вашем входном массиве, и если номер не найден в соответствующем столбце , вы увеличиваете j и переходите к следующему столбцу. Самая важная вещь в бинарном поиске - «Массив, в котором вы ищете, всегда должен быть отсортирован». Поскольку здесь вы ищете столбцы, все ваши столбцы будут отсортированы! Который выглядит несортированным в коде выше! Это основная причина, почему вы не находите большинство элементов. Таким образом, ваш входной массив будет выглядеть примерно так (если вы хотите применить бинарный поиск) ::

int mat[SIZE][SIZE] = { 0,1,5,2, 
         8,6,7,7, 
         11,7,7,10, 
         11,12,9,11 } 

Все столбцы отсортированных в порядке возрастания здесь!

2) Значение переменной NOT_FOUND вы установили ее в 1, и из вашей функции вы возвращаете номер столбца с того места, где вы нашли этот элемент. Итак, если вы нашли элемент в 2D-массиве в столбце 1, ваша программа напечатает Element Not Found, потому что условие if (index == NOT_FOUND) оценивает true, если элемент был найден в столбце 1. Таким образом, лучшим решением было бы изменить значение NOT_FOUND на некоторое отрицательное значение, так как оно никогда не может быть номером столбца в действительном случае. Нечто подобное ::

const int NOT_FOUND = -1; 

Ideone ссылки код :: http://ideone.com/9cwHnY