Рубрики

Поиск элемента в отсортированной матрице

Дана отсортированная матрица mat [n] [m] и элемент 'x'. Найдите положение x в матрице, если оно присутствует, иначе выведите -1. Матрица сортируется таким образом, что все элементы в строке сортируются в порядке возрастания и для строки 'i', где 1 Input: mat [] [] = {{1, 5, 9}, {14, 20, 21 }, {30, 34, 43}} x = 14 Вывод: найдено в (1, 0) Вход: mat [] [] = {{1, 5, 9, 11}, {14, 20, 21, 26} , {30, 34, 43, 50}} x = 42 Выход: -1

Обратите внимание, что эта проблема отличается от поиска в строке и отсортированной по столбцу матрице . Здесь матрица сортируется более строго, так как первый элемент строки больше, чем последний элемент предыдущей строки.

Простое решение состоит в том, чтобы один за другим сравнивать x с каждым элементом матрицы. Если совпадения, то верните позицию. Если мы достигнем конца, вернем -1. Временная сложность этого решения составляет O (nxm).

Эффективным решением является приведение типа данного массива к массиву 1D, а затем применить бинарный поиск к массиву типа.

Другой эффективный подход , который не требует типизации, объясняется ниже.

1) Perform binary search on the middle column 
   till only two elements are left or till the
   middle element of some row in the search is
   the required element 'x'. This search is done
   to skip the rows that are not required
2) The two left elements must be adjacent. Consider
   the rows of two elements and do following
   a) check whether the element 'x' equals to the 
      middle element of any one of the 2 rows
   b) otherwise according to the value of the 
      element 'x' check whether it is present in 
      the 1st half of 1st row, 2nd half of 1st row, 
      1st half of 2nd row or 2nd half of 2nd row. 

Note: This approach works for the matrix n x m 
      where 2 

Example:

Consider:    | 1  2  3  4| 
x = 3, mat = | 5  6  7  8|   Middle column:
             | 9 10 11 12|    = {2, 6, 10, 14}
             |13 14 15 16|   perform binary search on them
                             since, x 2  3  4| 
x = 3, mat = | 5  6  7  8|   Check whether element is present
                             on the middle elements of these
                             rows = {2, 6}
                             x != 2 or 6
If not, consider the four sub-parts
1st half of 1st row = {1}, 2nd half of 1st row = {3, 4}
1st half of 2nd row = {5}, 2nd half of 2nd row = {7, 8}

According the value of 'x' it will be searched in the
2nd half of 1st row = {3, 4} and found at (i, j): (0, 2)                              

C ++

// реализация C ++ для поиска элемента в
// отсортированная матрица
#include <bits/stdc++.h>

using namespace std;

  

const int MAX = 100;

  
// Эта функция выполняет бинарный поиск для х в i-м
// строка. Это делает поиск от mat [i] [j_low] к
// mat [i] [j_high]

void binarySearch(int mat[][MAX], int i, int j_low,

                                int j_high, int x)

{

    while (j_low <= j_high)

    {

        int j_mid = (j_low + j_high) / 2;

  

        // Элемент найден

        if (mat[i][j_mid] == x)

        {

            cout << "Found at (" << i << ", "

                 << j_mid << ")";

            return;

        }

  

        else if (mat[i][j_mid] > x)

            j_high = j_mid - 1;

  

        else

            j_low = j_mid + 1;

    }

  

    // элемент не найден

    cout << "Element no found";

}

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

void sortedMatrixSearch(int mat[][MAX], int n,

                                  int m, int x)

{

    // Однорядная матрица

    if (n == 1)

    {

        binarySearch(mat, 0, 0, m-1, x);

        return;

    }

  

    // Делаем бинарный поиск в среднем столбце.

    // Условие завершить цикл, когда

    // найдены 2 нужные строки

    int i_low = 0;

    int i_high = n-1;

    int j_mid = m/2;

    while ((i_low+1) < i_high)

    {

        int i_mid = (i_low + i_high) / 2;

  

        // элемент найден

        if (mat[i_mid][j_mid] == x)

        {

            cout << "Found at (" << i_mid << ", "

                 << j_mid << ")";

            return;

        }

  

        else if (mat[i_mid][j_mid] > x)

            i_high = i_mid;

  

        else

            i_low = i_mid;

    }

  

    // Если элемент присутствует в середине

    // две строки

    if (mat[i_low][j_mid] == x)

        cout << "Found at (" << i_low << ","

             << j_mid << ")";

    else if (mat[i_low+1][j_mid] == x)

        cout << "Found at (" << (i_low+1)

             << ", " << j_mid << ")";

  

    // Элемент поиска в 1-й половине 1-го ряда

    else if (x <= mat[i_low][j_mid-1])

        binarySearch(mat, i_low, 0, j_mid-1, x);

  

    // Поиск элемента во 2-й половине 1-й строки

    else if (x >= mat[i_low][j_mid+1]  &&

             x <= mat[i_low][m-1])

       binarySearch(mat, i_low, j_mid+1, m-1, x);

  

    // Поиск элемента в первой половине второй строки

    else if (x <= mat[i_low+1][j_mid-1])

        binarySearch(mat, i_low+1, 0, j_mid-1, x);

  

    // поиск элемента во 2-й половине 2-й строки

    else

        binarySearch(mat, i_low+1, j_mid+1, m-1, x);

}

  
// Программа драйвера для тестирования выше

int main()

{

    int n = 4, m = 5, x = 8;

    int mat[][MAX] = {{0, 6, 8, 9, 11},

                     {20, 22, 28, 29, 31},

                     {36, 38, 50, 61, 63},

                     {64, 66, 100, 122, 128}};

  

    sortedMatrixSearch(mat, n, m, x);

    return 0;

}

Джава

// реализация Java для поиска
// элемент в отсортированной матрице

import java.io.*;

  

class GFG 

{

    static int MAX = 100;

      

    // Эта функция выполняет бинарный поиск для х в i-м

    // строка. Это делает поиск от mat [i] [j_low] к

    // mat [i] [j_high]

    static void binarySearch(int mat[][], int i, int j_low,

                                    int j_high, int x)

    {

        while (j_low <= j_high)

        {

            int j_mid = (j_low + j_high) / 2;

      

            // Элемент найден

            if (mat[i][j_mid] == x)

            {

                System.out.println ( "Found at (" + i 

                                     + ", " + j_mid +")");

                return;

            }

      

            else if (mat[i][j_mid] > x)

                j_high = j_mid - 1;

      

            else

                j_low = j_mid + 1;

        }

      

        // элемент не найден

        System.out.println ( "Element no found");

    }

      

    // Функция для выполнения бинарного поиска в середине

    // значения строки, чтобы получить желаемую пару строк

    // где можно найти элемент

    static void sortedMatrixSearch(int mat[][], int n,

                                         int m, int x)

    {

        // Однорядная матрица

        if (n == 1)

        {

            binarySearch(mat, 0, 0, m - 1, x);

            return;

        }

      

        // Делаем бинарный поиск в среднем столбце.

        // Условие завершить цикл, когда

        // найдены 2 нужные строки

        int i_low = 0;

        int i_high = n - 1;

        int j_mid = m / 2;

        while ((i_low + 1) < i_high)

        {

            int i_mid = (i_low + i_high) / 2;

      

            // элемент найден

            if (mat[i_mid][j_mid] == x)

            {

                System.out.println ( "Found at (" + i_mid +", "

                                    + j_mid +")");

                return;

            }

      

            else if (mat[i_mid][j_mid] > x)

                i_high = i_mid;

      

            else

                i_low = i_mid;

        }

      

        // Если элемент присутствует на

        // середина двух рядов

        if (mat[i_low][j_mid] == x)

            System.out.println ( "Found at (" + i_low + ","

                                 + j_mid +")");

        else if (mat[i_low + 1][j_mid] == x)

            System.out.println ( "Found at (" + (i_low + 1)

                                + ", " + j_mid +")");

      

        // Элемент поиска в 1-й половине 1-го ряда

        else if (x <= mat[i_low][j_mid - 1])

            binarySearch(mat, i_low, 0, j_mid - 1, x);

      

        // Поиск элемента во 2-й половине 1-й строки

        else if (x >= mat[i_low][j_mid + 1] &&

                 x <= mat[i_low][m - 1])

        binarySearch(mat, i_low, j_mid + 1, m - 1, x);

      

        // Поиск элемента в первой половине второй строки

        else if (x <= mat[i_low + 1][j_mid - 1])

            binarySearch(mat, i_low + 1, 0, j_mid - 1, x);

      

        // поиск элемента во 2-й половине 2-й строки

        else

            binarySearch(mat, i_low + 1, j_mid + 1, m - 1, x);

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        int n = 4, m = 5, x = 8;

        int mat[][] = {{0, 6, 8, 9, 11},

                       {20, 22, 28, 29, 31},

                       {36, 38, 50, 61, 63},

                       {64, 66, 100, 122, 128}};

      

        sortedMatrixSearch(mat, n, m, x);

          

    }

}

  
// Этот код предоставлен vt_m

C #

// C # реализация для поиска
// элемент в отсортированной матрице

using System;

  

class GFG 

{

    // Эта функция выполняет бинарный поиск для х в i-м

    // строка. Это делает поиск от mat [i] [j_low] к

    // mat [i] [j_high]

    static void binarySearch(int [,]mat, int i, int j_low,

                                        int j_high, int x)

    {

        while (j_low <= j_high)

        {

            int j_mid = (j_low + j_high) / 2;

      

            // Элемент найден

            if (mat[i,j_mid] == x)

            {

                Console.Write ( "Found at (" + i +

                                ", " + j_mid +")");

                return;

            }

      

            else if (mat[i,j_mid] > x)

                j_high = j_mid - 1;

      

            else

                j_low = j_mid + 1;

        }

      

        // элемент не найден

        Console.Write ( "Element no found");

    }

      

    // Функция для выполнения бинарного поиска в середине

    // значения строки, чтобы получить желаемую пару строк

    // где можно найти элемент

    static void sortedMatrixSearch(int [,]mat, int n,

                                        int m, int x)

    {

        // Однорядная матрица

        if (n == 1)

        {

            binarySearch(mat, 0, 0, m - 1, x);

            return;

        }

      

        // Делаем бинарный поиск в среднем столбце.

        // Условие завершить цикл, когда

        // найдены 2 нужные строки

        int i_low = 0;

        int i_high = n - 1;

        int j_mid = m / 2;

        while ((i_low + 1) < i_high)

        {

            int i_mid = (i_low + i_high) / 2;

      

            // элемент найден

            if (mat[i_mid,j_mid] == x)

            {

                  

                Console.Write ( "Found at (" + i_mid + 

                                ", "    + j_mid +")");

                return;

            }

      

            else if (mat[i_mid,j_mid] > x)

                i_high = i_mid;

      

            else

                i_low = i_mid;

        }

      

        // Если элемент присутствует на

        // середина двух рядов

        if (mat[i_low,j_mid] == x)

        Console.Write ( "Found at (" + i_low +

                           "," + j_mid +")");

        else if (mat[i_low + 1,j_mid] == x)

        Console.Write ( "Found at (" + (i_low

                   + 1) + ", " + j_mid +")");

      

        // Элемент поиска в 1-й половине 1-го ряда

        else if (x <= mat[i_low,j_mid - 1])

            binarySearch(mat, i_low, 0, j_mid - 1, x);

      

        // Поиск элемента во 2-й половине 1-й строки

        else if (x >= mat[i_low,j_mid + 1] &&

                 x <= mat[i_low,m - 1])

        binarySearch(mat, i_low, j_mid + 1, m - 1, x);

      

        // Поиск элемента в первой половине второй строки

        else if (x <= mat[i_low + 1,j_mid - 1])

            binarySearch(mat, i_low + 1, 0, j_mid - 1, x);

      

        // поиск элемента во 2-й половине 2-й строки

        else

            binarySearch(mat, i_low + 1, j_mid + 1, m - 1, x);

    }

      

    // Драйвер программы

    public static void Main (String[] args) 

    {

        int n = 4, m = 5, x = 8;

        int [,]mat = {{0, 6, 8, 9, 11},

                    {20, 22, 28, 29, 31},

                    {36, 38, 50, 61, 63},

                    {64, 66, 100, 122, 128}};

      

        sortedMatrixSearch(mat, n, m, x);

    }

}

  
// Этот код предоставлен parashar ...


Выход:

Found at (0,2)

Временная сложность: O (log n + log m). O (Log n) требуется время, чтобы найти две нужные строки. Тогда O (Log m) время требуется для двоичного поиска в одной из четырех частей с размером, равным m / 2.

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Поиск элемента в отсортированной матрице

0.00 (0%) 0 votes