Dada una array nxn y un entero x , encuentre la posición de x en la array si está presente. De lo contrario, imprima «Elemento no encontrado».
Cada fila y columna de la array se ordena en orden creciente. El algoritmo diseñado debe tener una complejidad de tiempo lineal.
C++
// C++ program to search an element in row-wise
// and column-wise sorted matrix
#include <bits/stdc++.h>
using namespace std;
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
// traverse through the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
// if the element is found
if (mat[i][j] == x) {
cout << "Element found at (" << i << ", "
<< j << ")\n";
return 1;
}
}
cout << "n Element not found";
return 0;
}
// Driver code
int main()
{
int mat[4][4] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to search an element in row-wise
// and column-wise sorted matrix
#include <stdio.h>
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
// traverse through the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
// if the element is found
if (mat[i][j] == x) {
printf("Element found at (%d, %d)\n", i, j);
return 1;
}
}
printf("Element not found");
return 0;
}
// Driver code
int main()
{
int mat[4][4] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to search an element in row-wise
// and column-wise sorted matrix
class GFG {
static int search(int[][] mat, int n, int x)
{
if (n == 0)
return -1;
// traverse through the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
// if the element is found
if (mat[i][j] == x) {
System.out.print("Element found at ("
+ i + ", " + j
+ ")\n");
return 1;
}
}
System.out.print(" Element not found");
return 0;
}
public static void main(String[] args)
{
int mat[][] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python program to search an element in row-wise
# and column-wise sorted matrix
# Searches the element x in mat[][]. If the
# element is found, then prints its position
# and returns true, otherwise prints "not found"
# and returns false
def search(mat, n, x):
if(n == 0):
return -1
# Traverse through the matrix
for i in range(n):
for j in range(n):
# If the element is found
if(mat[i][j] == x):
print("Element found at (", i, ",", j, ")")
return 1
print(" Element not found")
return 0
# Driver code
mat = [[10, 20, 30, 40], [15, 25, 35, 45],[27, 29, 37, 48],[32, 33, 39, 50]]
search(mat, 4, 29)
# This code is contributed by rag2127
C#
// C# program to search an element in row-wise
// and column-wise sorted matrix
using System;
class GFG{
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
static int search(int[,] mat, int n, int x)
{
if (n == 0)
return -1;
// Traverse through the matrix
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
// If the element is found
if (mat[i,j] == x)
{
Console.Write("Element found at (" + i +
", " + j + ")\n");
return 1;
}
}
Console.Write(" Element not found");
return 0;
}
// Driver code
static public void Main()
{
int[,] mat = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Java Script program to search an element in row-wise
// and column-wise sorted matrix
function search(mat,n,x) {
if (n == 0)
return -1;
// traverse through the matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++)
// if the element is found
if (mat[i][j] == x) {
document.write("Element found at ("
+ i + ", " + j
+ ")<br>");
return 1;
}
}
document.write(" Element not found");
return 0;
}
let mat = [[ 10, 20, 30, 40 ],
[15, 25, 35, 45] ,
[ 27, 29, 37, 48 ],
[ 32, 33, 39, 50 ]];
search(mat, 4, 29);
//contributed by 171fa07058
</script>
C++
// C++ program to search an element in row-wise
// and column-wise sorted matrix
#include <bits/stdc++.h>
using namespace std;
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
int smallest = mat[0][0], largest = mat[n - 1][n - 1];
if (x < smallest || x > largest)
return -1;
// set indexes for top right element
int i = 0, j = n - 1;
while (i < n && j >= 0)
{
if (mat[i][j] == x)
{
cout << "Element found at "
<< i << ", " << j;
return 1;
}
if (mat[i][j] > x)
j--;
// Check if mat[i][j] < x
else
i++;
}
cout << "n Element not found";
return 0;
}
// Driver code
int main()
{
int mat[4][4] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
return 0;
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
C
// C program to search an element in row-wise
// and column-wise sorted matrix
#include <stdio.h>
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
int smallest = mat[0][0], largest = mat[n - 1][n - 1];
if (x < smallest || x > largest)
return -1;
// set indexes for top right element
int i = 0, j = n - 1;
while (i < n && j >= 0)
{
if (mat[i][j] == x)
{
printf("Element found at %d, %d", i, j);
return 1;
}
if (mat[i][j] > x)
j--;
else // if mat[i][j] < x
i++;
}
printf("n Element not found");
return 0; // if ( i==n || j== -1 )
}
// driver program to test above function
int main()
{
int mat[4][4] = {
{ 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 },
};
search(mat, 4, 29);
return 0;
}
Java
// JAVA Code for Search in a row wise and
// column wise sorted matrix
class GFG {
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
private static void search(int[][] mat,
int n, int x)
{
// set indexes for top right
int i = 0, j = n - 1;
// element
while (i < n && j >= 0)
{
if (mat[i][j] == x)
{
System.out.print("Element found at " +
i + " " + j);
return;
}
if (mat[i][j] > x)
j--;
else // if mat[i][j] < x
i++;
}
System.out.print("n Element not found");
return; // if ( i==n || j== -1 )
}
// driver program to test above function
public static void main(String[] args)
{
int mat[][] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to search an element
# in row-wise and column-wise sorted matrix
# Searches the element x in mat[][]. If the
# element is found, then prints its position
# and returns true, otherwise prints "not found"
# and returns false
def search(mat, n, x):
i = 0
# set indexes for top right element
j = n - 1
while ( i < n and j >= 0 ):
if (mat[i][j] == x ):
print("Element found at ", i, ", ", j)
return 1
if (mat[i][j] > x ):
j -= 1
# if mat[i][j] < x
else:
i += 1
print("Element not found")
return 0 # if (i == n || j == -1 )
# Driver Code
mat = [ [10, 20, 30, 40],
[15, 25, 35, 45],
[27, 29, 37, 48],
[32, 33, 39, 50] ]
search(mat, 4, 29)
# This code is contributed by Anant Agarwal.
C#
// C# Code for Search in a row wise and
// column wise sorted matrix
using System;
class GFG
{
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
private static void search(int[, ] mat,
int n, int x)
{
// set indexes for top right
// element
int i = 0, j = n - 1;
while (i < n && j >= 0)
{
if (mat[i, j] == x)
{
Console.Write("Element found at "
+ i + ", " + j);
return;
}
if (mat[i, j] > x)
j--;
else // if mat[i][j] < x
i++;
}
Console.Write("n Element not found");
return; // if ( i==n || j== -1 )
}
// driver program to test above function
public static void Main()
{
int[, ] mat = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to search an
// element in row-wise and
// column-wise sorted matrix
/* Searches the element $x
in mat[][]. If the element is
found, then prints its position
and returns true, otherwise prints
"not found" and returns false */
function search(&$mat, $n, $x)
{
$i = 0;
$j = $n - 1; // set indexes for
// top right element
while ($i < $n && $j >= 0)
{
if ($mat[$i][$j] == $x)
{
echo "Element found at " . $i.
", " . $j;
return 1;
}
if ($mat[$i][$j] > $x)
$j--;
else // if $mat[$i][$j] < $x
$i++;
}
echo "n Element not found";
return 0; // if ( $i==$n || $j== -1 )
}
// Driver Code
$mat = array(array(10, 20, 30, 40),
array(15, 25, 35, 45),
array(27, 29, 37, 48),
array(32, 33, 39, 50));
search($mat, 4, 29);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// JAVA SCRIPT Code for Search in a row wise and
// column wise sorted matrix
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
function search(mat,n,x){
// set indexes for top right
let i = 0, j = n - 1;
// element
while (i < n && j >= 0)
{
if (mat[i][j] == x)
{
document.write("Element found at " +
i + " " + j);
return;
}
if (mat[i][j] > x)
j--;
else // if mat[i][j] < x
i++;
}
document.write("n Element not found");
return; // if ( i==n || j== -1 )
}
// driver program to test above function
let mat = [[10, 20, 30, 40 ],
[ 15, 25, 35, 45 ],
[ 27, 29, 37, 48 ],
[ 32, 33, 39, 50 ]];
search(mat, 4, 29);
// This code is contributed by bobby
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA