Учитывая матричную структуру целых чисел, отсортированную по строкам, как реализовать бинарный поиск?

Предположим, у меня есть матрица структура, которая выглядит следующим образом:Учитывая матричную структуру целых чисел, отсортированную по строкам, как реализовать бинарный поиск?

1 3 4 
7 8 9 
11 15 18

и эта структура передается мне как массив из 2-D под названием «ppArr».

Так ppArr[0][0] = 1, ppArr[0][1]=3,..., ppArr[2][2] = 18.

Я пытаюсь реализовать следующую функцию:

bool elementExists(int ** ppArr, int target, int rowSize, int colSize);

так elementExist(ppArr, 9,3,3) возвращает true, но elementExists(ppArr, 14,3,3) возвращает false.

У меня есть общее представление о том, как решить эту проблему, вот некоторые псевдокод:

// loop until found or no more elements left 



while (true) { 
    int rowMp = rowSize/2; // computing row mid point 
    int colMp = colSize/2; // computing column mid point 
// check if midpoint value is equal to target 

    if(target == ppArr[rowMp][colMp]){ 
     // found it 
     return true; 
    } 
    else{ 

     // check bounds 

     // if we are on the last element 
     if (rowMp == rowSize-1) && (colMp == colSize =1){ 
      // we have reached the end of our search with no success 
      return false; 
     } 

     // if we are on the first element 
     if (rowMp == 0 && colMp == 0){ 
      // we have reached the start point of structure with no success 
      return false; 
     } 



     // case 1 - target bigger than midpint 
     if (target > ppArr[rowMp][colMp]){ 
      // TODO: how do I increment my rowMP and colMP here? I'm stuck 

     } 

     // case 2 - target smaller than midpoint 
     if (target < ppArr[rowMidPointIndex][colMidPointIndex]){ 
      // TODO: how do i decrement my rowMP and colMP here? 
     } 
    } 
}

источник

2015-07-29 user1068636

Это классический вопрос с алгоритмами, и я почти уверен, что его спрашивали здесь раньше. Вы можете выполнить поиск здесь, чтобы узнать, можете ли вы найти ответ. – templatetypedef

Является ли весь набор элементов отсортированными, а затем заполнены по строкам, или просто, что каждая строка сортируется без какого-либо конкретного отношения к другим строкам? –

Я бы сказал, это поможет: http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/ – KillaBytes

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

Если каждая строка сортируется, но между строками нет конкретной связи, вам придется искать каждую строку независимо.

Если ни одно из этих описаний не соответствует вашей проблеме, вам нужно лучше объяснить, какие ограничения на заполнение массива.

источник

2015-07-29 17:55:09

Учитывая матричную структуру целых чисел, отсортированную по строкам, как реализовать бинарный поиск?

ответ

Смежные вопросы