Buscar en una array 2D ordenada (almacenada en orden principal de fila)

Dado un número entero ‘K’ y una array bidimensional ordenada por filas, es decir, la array tiene las siguientes propiedades: 
 

  • Los números enteros en cada fila se ordenan de izquierda a derecha.
  • El primer entero de cada fila es mayor que el último entero de la fila anterior.

La tarea es encontrar si el entero ‘K’ está presente en la array o no. Si está presente, imprima ‘Encontrado’; de lo contrario, imprima ‘No encontrado’.
Ejemplos: 
 

Input: mat = {
  {1,   3,  5,  7},
  {10, 11, 16, 20},
  {23, 30, 34, 50}}
  K = 3
Output: Found

Input: mat = {
  {1,   3,  5,  7},
  {10, 11, 16, 20},
  {23, 30, 34, 50}}
  K = 13
Output: Not found

Hemos discutido una implementación en Elemento de búsqueda en una array ordenada . En esta publicación, se proporciona una mejor implementación.
Enfoque: La idea es utilizar el enfoque divide y vencerás para resolver este problema. 
 

  • Primero aplique la búsqueda binaria para encontrar la fila en particular, es decir, ‘K’ se encuentra entre el primero y el último elemento de esa fila.
  • Luego aplique una búsqueda binaria simple en esa fila para encontrar si ‘K’ está presente en esa fila o no.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find whether
// a given element is present
// in the given 2-D matrix
#include <bits/stdc++.h>
using namespace std;
 
#define M 3
#define N 4
 
// Basic binary search to
// find an element in a 1-D array
bool binarySearch1D(int arr[], int K)
{
    int low = 0;
    int high = N - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        // if element found return true
        if (arr[mid] == K)
            return true;
 
        // if middle less than K then
        // skip the left part of the
        // array else skip the right part
        if (arr[mid] < K)
            low = mid + 1;
        else
            high = mid - 1;
    }
 
    // if not found return false
    return false;
}
 
// Function to search an element
// in a matrix based on
// Divide and conquer approach
bool searchMatrix(int matrix[M][N], int K)
{
    int low = 0;
    int high = M - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        // if the element lies in the range
        // of this row then call
        // 1-D binary search on this row
        if (K >= matrix[mid][0]
            && K <= matrix[mid][N - 1])
            return binarySearch1D(matrix[mid], K);
 
        // if the element is less than the
        // starting element of that row then
        // search in upper rows else search
        // in the lower rows
        if (K < matrix[mid][0])
            high = mid - 1;
        else
            low = mid + 1;
    }
 
    // if not found
    return false;
}
 
// Driver code
int main()
{
    int matrix[M][N] = { { 1, 3, 5, 7 },
                         { 10, 11, 16, 20 },
                         { 23, 30, 34, 50 } };
    int K = 3;
    if (searchMatrix(matrix, K))
        cout << "Found" << endl;
    else
        cout << "Not found" << endl;
}

Java

// Java program to find whether
// a given element is present
// in the given 2-D matrix
 
public class GFG {
 
    static final int M = 3;
    static final int N = 4;
 
    // Basic binary search to
    // find an element in a 1-D array
    static boolean binarySearch1D(int arr[], int K)
    {
        int low = 0;
        int high = N - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
 
            // if element found return true
            if (arr[mid] == K) {
                return true;
            }
 
            // if middle less than K then
            // skip the left part of the
            // array else skip the right part
            if (arr[mid] < K) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
 
        // if not found return false
        return false;
    }
 
    // Function to search an element
    // in a matrix based on
    // Divide and conquer approach
    static boolean searchMatrix(int matrix[][], int K)
    {
        int low = 0;
        int high = M - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
 
            // if the element lies in the range
            // of this row then call
            // 1-D binary search on this row
            if (K >= matrix[mid][0]
                && K <= matrix[mid][N - 1]) {
                return binarySearch1D(matrix[mid], K);
            }
 
            // if the element is less than the
            // starting element of that row then
            // search in upper rows else search
            // in the lower rows
            if (K < matrix[mid][0]) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
 
        // if not found
        return false;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int matrix[][] = { { 1, 3, 5, 7 },
                           { 10, 11, 16, 20 },
                           { 23, 30, 34, 50 } };
        int K = 3;
        if (searchMatrix(matrix, K)) {
            System.out.println("Found");
        }
        else {
            System.out.println("Not found");
        }
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 program to find whether a given
# element is present in the given 2-D matrix
 
M = 3
N = 4
 
# Basic binary search to find an element
# in a 1-D array
def binarySearch1D(arr, K):
    low = 0
    high = N - 1
    while (low <= high):
        mid = low + int((high - low) / 2)
 
        # if element found return true
        if (arr[mid] == K):
            return True
 
        # if middle less than K then skip
        # the left part of the array
        # else skip the right part
        if (arr[mid] < K):
            low = mid + 1
        else:
            high = mid - 1
 
    # if not found return false
    return False
 
# Function to search an element in a matrix
# based on Divide and conquer approach
def searchMatrix(matrix, K):
    low = 0
    high = M - 1
    while (low <= high):
        mid = low + int((high - low) / 2)
 
        # if the element lies in the range
        # of this row then call
        # 1-D binary search on this row
        if (K >= matrix[mid][0] and
            K <= matrix[mid][N - 1]):
            return binarySearch1D(matrix[mid], K)
 
        # if the element is less than the
        # starting element of that row then
        # search in upper rows else search
        # in the lower rows
        if (K < matrix[mid][0]):
            high = mid - 1
        else:
            low = mid + 1
 
    # if not found
    return False
 
# Driver code
if __name__ == '__main__':
    matrix = [[1, 3, 5, 7],
              [10, 11, 16, 20],
              [23, 30, 34, 50]]
    K = 3
    if (searchMatrix(matrix, K)):
        print("Found")
    else:
        print("Not found")
 
# This code is contributed by
# Shashank_Sharma

C#

// C# program to find whether
// a given element is present
// in the given 2-D matrix
using System;
     
class GFG
{
 
    static int M = 3;
    static int N = 4;
 
    // Basic binary search to
    // find an element in a 1-D array
    static bool binarySearch1D(int []arr, int K)
    {
        int low = 0;
        int high = N - 1;
        while (low <= high)
        {
            int mid = low + (high - low) / 2;
 
            // if element found return true
            if (arr[mid] == K)
            {
                return true;
            }
 
            // if middle less than K then
            // skip the left part of the
            // array else skip the right part
            if (arr[mid] < K)
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
 
        // if not found return false
        return false;
    }
 
    // Function to search an element
    // in a matrix based on
    // Divide and conquer approach
    static bool searchMatrix(int [,]matrix, int K)
    {
        int low = 0;
        int high = M - 1;
        while (low <= high)
        {
            int mid = low + (high - low) / 2;
 
            // if the element lies in the range
            // of this row then call
            // 1-D binary search on this row
            if (K >= matrix[mid,0]
                && K <= matrix[mid,N - 1])
            {
                return binarySearch1D(GetRow(matrix,mid), K);
            }
 
            // if the element is less than the
            // starting element of that row then
            // search in upper rows else search
            // in the lower rows
            if (K < matrix[mid,0])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
 
        // if not found
        return false;
    }
    public static int[] GetRow(int[,] matrix, int row)
    {
        var rowLength = matrix.GetLength(1);
        var rowVector = new int[rowLength];
 
        for (var i = 0; i < rowLength; i++)
        rowVector[i] = matrix[row, i];
 
        return rowVector;
    }
     
    // Driver code
    public static void Main(String []args)
    {
        int [,]matrix = { { 1, 3, 5, 7 },
                        { 10, 11, 16, 20 },
                        { 23, 30, 34, 50 } };
        int K = 3;
        if (searchMatrix(matrix, K)) {
            Console.WriteLine("Found");
        }
        else {
        Console.WriteLine("Not found");
        }
    }
}
 
// This code contributed by Rajput-Ji

PHP

<?php
// Php program to find whether a given
// element is present in the given 2-D matrix
$M = 3;
$N = 4;
 
 
// Basic binary search to find an element
// in a 1-D array
function binarySearch1D($arr, $K)
{
     
    $low = 0;
    $high = $GLOBALS['N'] - 1;
    while ($low <= $high) {
        $mid = $low + (int)($high - $low) / 2;
 
// if element found return true
        if ($arr[$mid] == $K)
            return True;
 
// if middle less than K then skip
// the left part of the array
// else skip the right part
        if ($arr[$mid] < $K)
            $low = $mid + 1;
        else
            $high = $mid - 1;
    }
// if not found return false
    return False;
}
 
// Function to search an element in a matrix
// based on Divide and conquer approach
function searchMatrix($matrix, $K)
{
     
    $low = 0;
    $high = $GLOBALS['M']-1;
    while ($low <= $high)
    {
        $mid = $low + (int)($high - $low) / 2;
 
// if the element lies in the range
// of this row then call
// 1-D binary search on this row
        if ($K >= $matrix[$mid][0] && $K <= $matrix[$mid][$GLOBALS['N'] - 1])
            return binarySearch1D($matrix[$mid], $K);
 
// if the element is less than the
// starting element of that row then
// search in upper rows else search
// in the lower rows
        if ($K < $matrix[$mid][0])
            $high = $mid - 1;
        else
            $low = $mid + 1;
    }
 
// if not found
    return False;
}
 
// Driver code
 
$matrix = array([1, 3, 5, 7],
                [10, 11, 16, 20],
                [23, 30, 34, 50]);
$K = 3;
$M = 3;
$N = 4;
if (searchMatrix($matrix, $K))
echo "Found";
else
echo "Not found";
 
// This code is contributed by
// Srathore
?>

Javascript

<script>
 
// Javascript program to find whether
// a given element is present
// in the given 2-D matrix
 
var M = 3;
var N = 4;
 
// Basic binary search to
// find an element in a 1-D array
function binarySearch1D(arr, K)
{
    var low = 0;
    var high = N - 1;
    while (low <= high) {
        var mid = low + parseInt((high - low) / 2);
 
        // if element found return true
        if (arr[mid] == K)
            return true;
 
        // if middle less than K then
        // skip the left part of the
        // array else skip the right part
        if (arr[mid] < K)
            low = mid + 1;
        else
            high = mid - 1;
    }
 
    // if not found return false
    return false;
}
 
// Function to search an element
// in a matrix based on
// Divide and conquer approach
function searchMatrix(matrix, K)
{
    var low = 0;
    var high = M - 1;
    while (low <= high) {
        var mid = low + parseInt((high - low) / 2);
 
        // if the element lies in the range
        // of this row then call
        // 1-D binary search on this row
        if (K >= matrix[mid][0]
            && K <= matrix[mid][N - 1])
            return binarySearch1D(matrix[mid], K);
 
        // if the element is less than the
        // starting element of that row then
        // search in upper rows else search
        // in the lower rows
        if (K < matrix[mid][0])
            high = mid - 1;
        else
            low = mid + 1;
    }
 
    // if not found
    return false;
}
 
// Driver code
var matrix = [ [ 1, 3, 5, 7 ],
                     [ 10, 11, 16, 20 ],
                     [ 23, 30, 34, 50 ] ];
var K = 3;
if (searchMatrix(matrix, K))
    document.write( "Found" );
else
    document.write( "Not found" );
 
</script>
Producción: 

Found

 

Complejidad de tiempo: O(logN+LogM), N & M son filas y columnas de la array
Complejidad de espacio: O(1)

Publicación traducida automáticamente

Artículo escrito por geekoverflow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *