Searching Algorithms for 2D Arrays (Matrix)
Last Updated :
06 Apr, 2023
Linear Search in 2D Array:
Linear search is a simple and sequential searching algorithm. It is used to find whether a particular element is present in the array or not by traversing every element in the array. While searching in the 2D array is exactly the same but here all the cells need to be traversed In this way, any element is searched in a 2D array.
Below is the implementation for linear search in 2D arrays
C++
#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};
}
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;
}
|
Java
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
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]
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]}]")
|
C#
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 };
}
}
|
Javascript
<script>
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];
}
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]}]`);
</script>
|
Output
Element found at index: [1 2]
Time Complexity: O (N * M), where N is the number of rows and M is the number of columns.
Auxiliary Space: O(1)
Binary Search in a 2D Array:
Binary search is an efficient method of searching in an array. Binary search works on a sorted array. At each iteration the search space is divided in half, this is the reason why binary search is more efficient than linear search.
Why Binary Search is not useful for searching in unsorted arrays?
The basic condition to apply Binary Search anywhere in any algorithm is that the search space should be sorted. To perform a Binary search in the 2D array, the array needs to be sorted. Here is an unsorted 2D array is given, so applying Binary Search in an unsorted array is not possible. To apply Binary Search first the 2D array needs to be sorted in any order that itself takes (M*N)log(M*N) time. So the total time complexity to search any element here is O((M * N) log(M * N)) + O(N + M) which very poor when it is compared with the time complexity of Linear Search which is just O(N*M). Therefore, Linear Search is used for searching in an unsorted array, not Binary Search.
Below is the implementation for Binary search in 2D arrays:
C++
#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 };
}
if (arr[row][col] < target) {
row++;
}
else {
col--;
}
}
return { -1, -1 };
}
int main()
{
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 << "]";
}
|
Java
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 };
}
if (arr[row][col] < target) {
row++;
}
else {
col--;
}
}
return new int[] { -1, -1 };
}
public static void main(String[] args)
{
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
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]
if (arr[row][col] < target):
row += 1
else:
col -= 1
return [-1, -1]
if __name__ == '__main__':
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
ans = findAns(arr, 12)
print("Element found at index: ", ans)
|
C#
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 };
}
if (arr[row, col] < target) {
row++;
}
else {
col--;
}
}
return new int[] { -1, -1 };
}
public static void Main(string[] args)
{
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] + "]");
}
}
|
Javascript
<script>
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 ];
}
if (arr[row][col] < target) {
row++;
}
else {
col--;
}
}
return [ -1, -1 ];
}
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));
</script>
|
Output
Element found at index: [2, 3]
Time Complexity: O(N + M), where N is the number of rows and M is the number of columns.
Auxiliary Space: O(1)
Improved Binary Search in a 2D Array:
We can reduce the time by converting 2D array to 1D array. Add row one after another and search the item then convert it to 2D again.
Convert it to 1D array
Now apply normal binary search and get the result. Not necessary store the 1D in new array you can create it virtually by converting row, col value to 1D index vice-versa 1D to row, col value.
C++
#include <bits/stdc++.h>
using namespace std;
vector<int> findAns(vector<vector<int> > arr, int target)
{
int row = arr.size();
int col = arr[0].size();
int l = 0, h = row * col - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int tC = mid % col;
int tR = mid / col;
int val = arr[tR][tC];
if (val == target)
return { tR, tC };
if (val < target)
l = mid + 1;
else
h = mid - 1;
}
return { -1, -1 };
}
int main()
{
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 << "]";
return 0;
}
|
Java
import java.util.Arrays;
class GFG {
static int[] findAns(int[][] arr, int target)
{
int row = arr.length;
int col = arr[0].length;
int l = 0, h = row * col - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int tC = mid % col;
int tR = mid / col;
int val = arr[tR][tC];
if (val == target)
return new int[] { tR, tC };
if (val < target)
l = mid + 1;
else
h = mid - 1;
}
return new int[] { -1, -1 };
}
public static void main(String[] args)
{
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
def findAns(arr, target):
row = len(arr)
col = len(arr[0])
l, h = 0, row*col - 1
while(l <= h):
mid = l + (h-l)//2
tC = mid % col
tR = mid // col
val = arr[tR][tC]
if(val == target):
return [tR, tC]
if(val < target):
l = mid + 1
else:
h = mid - 1
return [-1, -1]
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
ans = findAns(arr, 12)
print("Element found at index:", ans)
|
C#
using System;
public class GFG {
static int[] findAns(int[, ] arr, int target)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);
int l = 0, h = row * col - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int tC = mid % col;
int tR = mid / col;
int val = arr[tR, tC];
if (val == target)
return new int[] { tR, tC };
if (val < target)
l = mid + 1;
else
h = mid - 1;
}
return new int[] { -1, -1 };
}
public static void Main(string[] args)
{
int[, ] arr = new int[, ] { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
int[] ans = findAns(arr, 12);
Console.WriteLine("Element found at index: ["
+ string.Join(", ", ans) + "]");
}
}
|
Javascript
function findAns( arr, target)
{
let row = arr.length;
let col = arr[0].length;
let l = 0, h = row * col - 1;
while (l <= h) {
let mid = l + Math.floor((h - l) / 2);
let tC = mid % col;
let tR = Math.floor(mid / col);
let val = arr[tR][tC];
if (val == target)
return [ tR, tC ];
if (val < target)
l = mid + 1;
else
h = mid - 1;
}
return [ -1, -1 ];
}
let arr = [ [ 1, 2, 3, 4 ],
[5, 6, 7, 8 ],
[ 9, 10, 11, 12 ]];
let ans = findAns(arr, 12);
let print = "Element found at index: [";
for (let i = 0; i < ans.length; i++) {
if (i == ans.length - 1)
print+= ans[i];
else
print+= ans[i] + ", ";
}
print+="]";
console.log(print);
|
Output
Element found at index: [2, 3]
Time Complexity: O(log N*M), where N is the number of rows and M is the number of columns since binary search will take the whole size of 1d array and here total elements in 2d array = M*N.
Auxiliary Space: O(1)
Please Login to comment...