Búsqueda lineal en array 2D:
La búsqueda lineal es un algoritmo de búsqueda simple y secuencial. Se utiliza para encontrar si un elemento en particular está presente en la array o no al recorrer cada elemento de la array. Mientras que la búsqueda en la array 2D es exactamente igual, pero aquí se deben recorrer todas las celdas. De esta manera, se busca cualquier elemento en una array 2D.
A continuación se muestra la implementación de la búsqueda lineal en arrays 2D
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
vector<int> linearSearch(vector<vector<int>> arr, int target)
{
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[i].size(); j++) {
if (arr[i][j] == target) {
return {i, j};
}
}
}
return {-1, -1};
}
// Driver code
int main()
{
vector<vector<int>> arr = { { 3, 12, 9 },
{ 5, 2, 89 },
{ 90, 45, 22 } };
int target = 89;
vector<int> ans = linearSearch(arr, target);
cout << "Element found at index: [" << ans[0] << " " <<ans[1] <<"]";
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Linear Search in 2D arrays
import java.util.Arrays;
public class GFG {
public static void main(String[] args)
{
int arr[][] = { { 3, 12, 9 },
{ 5, 2, 89 },
{ 90, 45, 22 } };
int target = 89;
int ans[] = linearSearch(arr, target);
System.out.println("Element found at index: "
+ Arrays.toString(ans));
}
static int[] linearSearch(int[][] arr, int target)
{
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (arr[i][j] == target) {
return new int[] { i, j };
}
}
}
return new int[] { -1, -1 };
}
}
Python3
# Python code for the above approach
def linearSearch (arr, target):
for i in range(len(arr)):
for j in range(len(arr[i])):
if (arr[i][j] == target):
return [i, j]
return [-1, -1]
# Driver code
arr = [[3, 12, 9], [5, 2, 89], [90, 45, 22]]
target = 89
ans = linearSearch(arr, target)
print(f"Element found at index: [{ans[0]} {ans[1]}]")
# This code is contributed by Saurabh Jaiswal
C#
// Linear Search in 2D arrays
using System;
public class GFG {
public static void Main(string[] args)
{
int[, ] arr = { { 3, 12, 9 },
{ 5, 2, 89 },
{ 90, 45, 22 } };
int target = 89;
int[] ans = linearSearch(arr, target);
Console.WriteLine("Element found at index: ["
+ ans[0] + "," + ans[1]+"]");
}
static int[] linearSearch(int[, ] arr, int target)
{
for (int i = 0; i < arr.GetLength(0); i++) {
for (int j = 0; j < arr.GetLength(1); j++) {
if (arr[i, j] == target) {
return new int[] { i, j };
}
}
}
return new int[] { -1, -1 };
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
const linearSearch = (arr, target) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[i].length; j++) {
if (arr[i][j] == target) {
return [i, j];
}
}
}
return [-1, -1];
}
// Driver code
let arr = [[3, 12, 9],
[5, 2, 89],
[90, 45, 22]];
let target = 89;
let ans = linearSearch(arr, target);
document.write(`Element found at index: [${ans[0]} ${ans[1]}]`);
// This code is contributed by rakeshsahni
</script>
Element found at index: [1 2]
Complejidad temporal: O (N * M), donde N es el número de filas y M es el número de columnas.
Espacio Auxiliar: O(1)
Búsqueda binaria en una array 2D:
La búsqueda binaria es un método eficiente de buscar en una array. La búsqueda binaria funciona en una array ordenada. En cada iteración el espacio de búsqueda se divide por la mitad, esta es la razón por la cual la búsqueda binaria es más eficiente que la búsqueda lineal.
¿Por qué la búsqueda binaria no es útil para buscar en arrays desordenadas?
La condición básica para aplicar la búsqueda binaria en cualquier lugar de cualquier algoritmo es que el espacio de búsqueda esté ordenado. Para realizar una búsqueda binaria en la array 2D, la array debe ordenarse. Aquí se proporciona una array 2D no ordenada, por lo que no es posible aplicar la búsqueda binaria en una array no ordenada. Para aplicar la búsqueda binaria primero, la array 2D debe ordenarse en cualquier orden que tome (M*N)log(M*N) tiempo. Entonces, la complejidad de tiempo total para buscar cualquier elemento aquí es O ((M * N) log (M * N)) + O (N + M), que es muy pobre cuando se compara con la complejidad de tiempo de Búsqueda lineal que es solo O (N*M) . Por lo tanto, la búsqueda lineal se usa para buscar en una array no ordenada, no la búsqueda binaria.
A continuación se muestra la implementación de la búsqueda binaria en arrays 2D:
C++
// Binary Search on sorted 2D array
#include <bits/stdc++.h>
using namespace std;
vector<int> findAns(vector<vector<int> > arr, int target)
{
int row = 0;
int col = arr[row].size() - 1;
while (row < arr.size() && col >= 0) {
if (arr[row][col] == target) {
return { row, col };
}
// Target lies in further row
if (arr[row][col] < target) {
row++;
}
// Target lies in previous column
else {
col--;
}
}
return { -1, -1 };
}
// Driver Code
int main()
{
// Binary search in sorted matrix
vector<vector<int> > arr = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
vector<int> ans = findAns(arr, 12);
cout << "Element found at index: [";
for (int i = 0; i < ans.size(); i++) {
if (i == ans.size() - 1)
cout << ans[i];
else
cout << ans[i] << ", ";
}
cout << "]";
}
// This code is contributed by Samim Hossain Mondal.
Java
// Binary Search on sorted 2D array
import java.util.Arrays;
class GFG {
static int[] findAns(int[][] arr, int target)
{
int row = 0;
int col = arr[row].length - 1;
while (row < arr.length && col >= 0) {
if (arr[row][col] == target) {
return new int[] { row, col };
}
// Target lies in further row
if (arr[row][col] < target) {
row++;
}
// Target lies in previous column
else {
col--;
}
}
return new int[] { -1, -1 };
}
// Driver Code
public static void main(String[] args)
{
// Binary search in sorted matrix
int arr[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
int[] ans = findAns(arr, 12);
System.out.println("Element found at index: "
+ Arrays.toString(ans));
}
}
Python3
# Binary Search on sorted 2D array
def findAns(arr, target):
row = 0
col = len(arr[row]) - 1
while (row < len(arr) and col >= 0):
if (arr[row][col] == target):
return [row, col]
# Target lies in further row
if (arr[row][col] < target):
row += 1
# Target lies in previous column
else:
col -= 1
return [-1, -1]
# Driver Code
if __name__ == '__main__':
# Binary search in sorted matrix
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
ans = findAns(arr, 12)
print("Element found at index: ", ans)
# This code contributed by shikhasingrajput
C#
// Binary Search on sorted 2D array
using System;
class GFG {
static int[] findAns(int[, ] arr, int target)
{
int row = 0;
int col = arr.GetLength(1) - 1;
while (row < arr.GetLength(0) && col >= 0) {
if (arr[row, col] == target) {
return new int[] { row, col };
}
// Target lies in further row
if (arr[row, col] < target) {
row++;
}
// Target lies in previous column
else {
col--;
}
}
return new int[] { -1, -1 };
}
// Driver Code
public static void Main(string[] args)
{
// Binary search in sorted matrix
int[, ] arr = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
int[] ans = findAns(arr, 12);
Console.Write("Element found at index: [");
int i = 0;
for (i = 0; i < ans.Length - 1; i++)
Console.Write(ans[i] + " ,");
Console.Write(ans[i] + "]");
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Binary Search on sorted 2D array
function findAns(arr , target)
{
var row = 0;
var col = arr[row].length - 1;
while (row < arr.length && col >= 0) {
if (arr[row][col] == target) {
return [ row, col ];
}
// Target lies in further row
if (arr[row][col] < target) {
row++;
}
// Target lies in previous column
else {
col--;
}
}
return [ -1, -1 ];
}
// Driver Code
// Binary search in sorted matrix
var arr = [ [ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ] ];
var ans = findAns(arr, 12);
document.write("Element found at index: "
+ (ans));
// This code is contributed by shikhasingrajput
</script>
Element found at index: [2, 3]
Complejidad temporal: O(N + M), donde N es el número de filas y M es el número de columnas.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por samughodake1808 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA