Search in row wise and column wise sorted matrix
The problem at hand involves searching for a specific value in a matrix that is both row-wise and column-wise sorted. This kind of matrix is sorted in such a way that each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Your task is to efficiently find a given value within this sorted matrix.
Problem Statement
Given a row-wise and column-wise sorted matrix mat, you need to determine whether a given value
value exists within the matrix. If it does, you should also find the index (row and column) where the
value is located.
Example
Consider the sorted matrix mat:
6 8 21 32 42
9 12 25 33 45
12 13 27 36 48
17 18 28 41 52
27 30 46 49 62If we want to find the value 28, the expected output should be "Index (3,2) : 28", indicating that the
value 28 is located at row 3 and column 2 of the matrix.
Idea to Solve
The problem can be solved using a divide and conquer approach. We start by comparing the middle element of the matrix with the target value. Based on this comparison, we can determine which part of the matrix the target value might lie in. This allows us to divide the search space into smaller sub-matrices and perform the same operation recursively.
Pseudocode
function search(matrix, currentRow, endRow, currentCol, endCol, value):
r = currentRow + (endRow - currentRow) / 2
c = currentCol + (endCol - currentCol) / 2
if matrix[r][c] == value:
print("Index (%d,%d) : %d" % (r, c, value))
return 1
else:
result = 0
if (r != endRow or c != currentCol):
result = search(matrix, currentRow, r, c, endCol, value)
if (result == 0 and currentRow == endRow and currentCol + 1 == endCol):
if matrix[currentRow][endCol] == value:
print("Index (%d,%d) : %d" % (currentRow, endCol, value))
result = 1
if (result == 0 and matrix[r][c] < value):
if r + 1 <= endRow:
result = search(matrix, r + 1, endRow, currentCol, endCol, value)
elif (result == 0):
if c - 1 >= currentCol:
result = search(matrix, currentRow, endRow, currentCol, c - 1, value)
return resultAlgorithm Explanation
- The base case handles an individual element and checks whether it matches the target value.
- The middle indices
randcare calculated to represent the middle of the current search space. - If the middle element is the target value, we print the index and return.
- If the middle element is not the target value, we explore different cases:
- We recursively search in the top-left sub-matrix if the target value might be present there.
- If the target value is not found in the top-left sub-matrix, we check the adjacent element on the right of the current row.
- We recursively search in the bottom-right sub-matrix if the target value might be present there.
- If the target value is not found in the bottom-right sub-matrix, we check the adjacent element on the left of the current column.
- This divide and conquer approach helps narrow down the search space efficiently.
Code Solution
// C program for
// Search in row wise and column wise sorted matrix
// Using divide and conquer algorithm
#include <stdio.h>
#define ROW 5
#define COL 5
int search(int matrix[ROW][COL],
int currentRow,
int endRow,
int currentCol,
int endCol,
int value)
{
int r = currentRow + (endRow - currentRow) / 2;
int c = currentCol + (endCol - currentCol) / 2;
if (matrix[r][c] == value)
{
// Element found on (r,c) location
printf("\n Index (%d,%d) : %d", r, c, value);
return 1;
}
else
{
int result = 0;
if (r != endRow || c != currentCol)
{
result = search(matrix, currentRow, r, c, endCol, value);
}
if (result == 0 && currentRow == endRow && currentCol + 1 == endCol)
{
if (matrix[currentRow][endCol] == value)
{
printf("\n Index (%d,%d) : %d", currentRow, endCol, value);
result = 1;
}
}
if (result == 0 && matrix[r][c] < value)
{
if (r + 1 <= endRow)
{
result = search(matrix,
r + 1,
endRow,
currentCol,
endCol,
value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = search(matrix,
currentRow,
endRow,
currentCol,
c - 1,
value);
}
}
return result;
}
}
void searchValue(int matrix[ROW][COL], int value)
{
int result = search(matrix, 0, ROW - 1, 0, COL - 1, value);
if (result == 0)
{
printf("\n None : %d", value);
}
}
int main(int argc, char
const *argv[])
{
int mat[ROW][COL] = {
{
6 , 8 , 21 , 32 , 42
},
{
9 , 12 , 25 , 33 , 45
},
{
12 , 13 , 27 , 36 , 48
},
{
17 , 18 , 28 , 41 , 52
},
{
27 , 30 , 46 , 49 , 62
}
};
searchValue(mat, 28);
searchValue(mat, 48);
return 0;
}Output
Index (3,2) : 28
Index (2,4) : 48// Java Program
// Search in row wise and column wise sorted matrix
public class Searching
{
public int search(int[][] matrix,
int currentRow, int endRow,
int currentCol, int endCol, int value)
{
int r = currentRow + (endRow - currentRow) / 2;
int c = currentCol + (endCol - currentCol) / 2;
if (matrix[r][c] == value)
{
// Element found on (r,c) location
System.out.print("\n Index (" + r + "," + c + ") : " + value);
return 1;
}
else
{
int result = 0;
if (r != endRow || c != currentCol)
{
result = search(matrix,
currentRow, r, c, endCol, value);
}
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
{
if (matrix[currentRow][endCol] == value)
{
System.out.print("\n Index (" +
currentRow + "," +
endCol + ") : " + value);
result = 1;
}
}
if (result == 0 && matrix[r][c] < value)
{
if (r + 1 <= endRow)
{
result = search(matrix, r + 1,
endRow, currentCol, endCol, value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = search(matrix, currentRow,
endRow, currentCol, c - 1, value);
}
}
return result;
}
}
public void searchValue(int[][] matrix, int value)
{
int row = matrix.length;
int col = matrix[0].length;
int result = search(matrix, 0, row - 1, 0, col - 1, value);
if (result == 0)
{
System.out.print("\n None : " + value);
}
}
public static void main(String args[])
{
Searching task = new Searching();
int[][] mat = {
{
6 , 8 , 21 , 32 , 42
},
{
9 , 12 , 25 , 33 , 45
},
{
12 , 13 , 27 , 36 , 48
},
{
17 , 18 , 28 , 41 , 52
},
{
27 , 30 , 46 , 49 , 62
}
};
task.searchValue(mat, 28);
task.searchValue(mat, 48);
}
}Output
Index (3,2) : 28
Index (2,4) : 48// Include header file
#include <iostream>
#define ROW 5
#define COL 5
using namespace std;
// C++ Program
// Search in row wise and column wise sorted matrix
class Searching
{
public: int search(int matrix[ROW][COL],
int currentRow, int endRow,
int currentCol,
int endCol,
int value)
{
int r = currentRow + (endRow - currentRow) / 2;
int c = currentCol + (endCol - currentCol) / 2;
if (matrix[r][c] == value)
{
// Element found on (r,c) location
cout << "\n Index (" << r
<< "," << c << ") : " << value;
return 1;
}
else
{
int result = 0;
if (r != endRow || c != currentCol)
{
result = this->search(matrix,
currentRow,
r, c,
endCol, value);
}
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
{
if (matrix[currentRow][endCol] == value)
{
cout << "\n Index ("
<< currentRow << ","
<< endCol << ") : " << value;
result = 1;
}
}
if (result == 0 && matrix[r][c] < value)
{
if (r + 1 <= endRow)
{
result = this->search(matrix, r + 1,
endRow, currentCol,
endCol, value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = this->search(matrix,
currentRow,
endRow,
currentCol,
c - 1,
value);
}
}
return result;
}
}
void searchValue(int matrix[ROW][COL], int value)
{
int result = this->search(matrix, 0,
ROW - 1, 0,
COL - 1, value);
if (result == 0)
{
cout << "\n None : " << value;
}
}
};
int main()
{
Searching *task = new Searching();
int mat[ROW][COL] = {
{
6 , 8 , 21 , 32 , 42
} , {
9 , 12 , 25 , 33 , 45
} , {
12 , 13 , 27 , 36 , 48
} , {
17 , 18 , 28 , 41 , 52
} , {
27 , 30 , 46 , 49 , 62
}
};
task->searchValue(mat, 28);
task->searchValue(mat, 48);
return 0;
}Output
Index (3,2) : 28
Index (2,4) : 48// Include namespace system
using System;
// Csharp Program
// Search in row wise and column wise sorted matrix
public class Searching
{
public int search(int[,] matrix,
int currentRow,
int endRow,
int currentCol,
int endCol,
int value)
{
int r = currentRow + (endRow - currentRow) / 2;
int c = currentCol + (endCol - currentCol) / 2;
if (matrix[r,c] == value)
{
// Element found on (r,c) location
Console.Write("\n Index (" + r + "," + c + ") : " + value);
return 1;
}
else
{
int result = 0;
if (r != endRow || c != currentCol)
{
result = this.search(matrix, currentRow,
r, c, endCol, value);
}
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
{
if (matrix[currentRow,endCol] == value)
{
Console.Write("\n Index (" +
currentRow + "," +
endCol + ") : " + value);
result = 1;
}
}
if (result == 0 && matrix[r,c] < value)
{
if (r + 1 <= endRow)
{
result = this.search(matrix, r + 1,
endRow, currentCol,
endCol, value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = this.search(matrix,
currentRow,
endRow,
currentCol,
c - 1, value);
}
}
return result;
}
}
public void searchValue(int[,] matrix, int value)
{
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
int result = this.search(matrix, 0,
row - 1, 0, col - 1, value);
if (result == 0)
{
Console.Write("\n None : " + value);
}
}
public static void Main(String[] args)
{
Searching task = new Searching();
int[,] mat = {
{
6 , 8 , 21 , 32 , 42
},
{
9 , 12 , 25 , 33 , 45
},
{
12 , 13 , 27 , 36 , 48
},
{
17 , 18 , 28 , 41 , 52
},
{
27 , 30 , 46 , 49 , 62
}
};
task.searchValue(mat, 28);
task.searchValue(mat, 48);
}
}Output
Index (3,2) : 28
Index (2,4) : 48package main
import "fmt"
// Go Program
// Search in row wise and column wise sorted matrix
func search(matrix[][] int, currentRow int, endRow int,
currentCol int, endCol int, value int) int {
var r int = currentRow + ((endRow - currentRow) / 2)
var c int = currentCol + ((endCol - currentCol) / 2)
if matrix[r][c] == value {
// Element found on (r,c) location
fmt.Print("\n Index (", r, ",", c, ") : ", value)
return 1
} else {
var result int = 0
if r != endRow || c != currentCol {
result = search(matrix, currentRow, r, c, endCol, value)
}
if result == 0 && currentRow == endRow && currentCol + 1 == endCol {
if matrix[currentRow][endCol] == value {
fmt.Print("\n Index (",
currentRow, ",", endCol, ") : ", value)
result = 1
}
}
if result == 0 && matrix[r][c] < value {
if (r + 1) <= endRow {
result = search(matrix, r + 1,
endRow, currentCol, endCol, value)
}
} else if result == 0 {
if (c - 1) >= currentCol {
result = search(matrix,
currentRow, endRow, currentCol, c - 1, value)
}
}
return result
}
}
func searchValue(matrix[][] int, value int) {
var row int = len(matrix)
var col int = len(matrix[0])
var result int = search(matrix, 0, row - 1, 0, col - 1, value)
if result == 0 {
fmt.Print("\n None : ", value)
}
}
func main() {
var mat = [][] int {
{ 6, 8, 21, 32 , 42 },
{ 9 , 12 , 25 , 33, 45 },
{ 12 , 13 , 27 , 36, 48 },
{ 17 , 18 , 28 , 41, 52 },
{ 27 , 30 , 46 , 49, 62 },
}
searchValue(mat, 28)
searchValue(mat, 48)
}Output
Index (3,2) : 28
Index (2,4) : 48<?php
// Php Program
// Search in row wise and column wise sorted matrix
class Searching
{
public function search($matrix, $currentRow,
$endRow, $currentCol,
$endCol, $value)
{
$r = $currentRow + (int)(($endRow - $currentRow) / 2);
$c = $currentCol + (int)(($endCol - $currentCol) / 2);
if ($matrix[$r][$c] == $value)
{
// Element found on (r,c) location
echo("\n Index (".$r.
",".$c.
") : ".$value);
return 1;
}
else
{
$result = 0;
if ($r != $endRow || $c != $currentCol)
{
$result = $this->search($matrix,
$currentRow, $r, $c,
$endCol, $value);
}
if ($result == 0 && $currentRow == $endRow &&
$currentCol + 1 == $endCol)
{
if ($matrix[$currentRow][$endCol] == $value)
{
echo("\n Index (".$currentRow.
",".$endCol.
") : ".$value);
$result = 1;
}
}
if ($result == 0 && $matrix[$r][$c] < $value)
{
if ($r + 1 <= $endRow)
{
$result = $this->search($matrix,
$r + 1, $endRow,
$currentCol,
$endCol, $value);
}
}
else if ($result == 0)
{
if ($c - 1 >= $currentCol)
{
$result = $this->search($matrix,
$currentRow, $endRow,
$currentCol, $c - 1, $value);
}
}
return $result;
}
}
public function searchValue($matrix, $value)
{
$row = count($matrix);
$col = count($matrix[0]);
$result = $this->search($matrix, 0,
$row - 1, 0,
$col - 1, $value);
if ($result == 0)
{
echo("\n None : ".$value);
}
}
}
function main()
{
$task = new Searching();
$mat = array(
array(6, 8, 21, 32, 42),
array(9, 12, 25, 33, 45),
array(12, 13, 27, 36, 48),
array(17, 18, 28, 41, 52),
array(27, 30, 46, 49, 62)
);
$task->searchValue($mat, 28);
$task->searchValue($mat, 48);
}
main();Output
Index (3,2) : 28
Index (2,4) : 48// Node JS Program
// Search in row wise and column wise sorted matrix
class Searching
{
search(matrix, currentRow, endRow, currentCol, endCol, value)
{
var r = currentRow + parseInt((endRow - currentRow) / 2);
var c = currentCol + parseInt((endCol - currentCol) / 2);
if (matrix[r][c] == value)
{
// Element found on (r,c) location
process.stdout.write("\n Index (" + r + "," + c + ") : " + value);
return 1;
}
else
{
var result = 0;
if (r != endRow || c != currentCol)
{
result = this.search(matrix, currentRow,
r, c, endCol, value);
}
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
{
if (matrix[currentRow][endCol] == value)
{
process.stdout.write("\n Index (" +
currentRow + "," + endCol + ") : " +
value);
result = 1;
}
}
if (result == 0 && matrix[r][c] < value)
{
if (r + 1 <= endRow)
{
result = this.search(matrix, r + 1,
endRow, currentCol, endCol, value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = this.search(matrix,
currentRow, endRow,
currentCol, c - 1, value);
}
}
return result;
}
}
searchValue(matrix, value)
{
var row = matrix.length;
var col = matrix[0].length;
var result = this.search(matrix, 0,
row - 1, 0, col - 1, value);
if (result == 0)
{
process.stdout.write("\n None : " + value);
}
}
}
function main()
{
var task = new Searching();
var mat = [
[6, 8, 21, 32, 42],
[9, 12, 25, 33, 45],
[12, 13, 27, 36, 48],
[17, 18, 28, 41, 52],
[27, 30, 46, 49, 62]
];
task.searchValue(mat, 28);
task.searchValue(mat, 48);
}
main();Output
Index (3,2) : 28
Index (2,4) : 48# Python 3 Program
# Search in row wise and column wise sorted matrix
class Searching :
def search(self, matrix, currentRow, endRow,
currentCol, endCol, value) :
r = currentRow + int((endRow - currentRow) / 2)
c = currentCol + int((endCol - currentCol) / 2)
if (matrix[r][c] == value) :
# Element found on (r,c) location
print("\n Index (", r ,",", c ,") : ", value, end = "")
return 1
else :
result = 0
if (r != endRow or c != currentCol) :
result = self.search(matrix, currentRow, r, c, endCol, value)
if (result == 0 and currentRow == endRow and
currentCol + 1 == endCol) :
if (matrix[currentRow][endCol] == value) :
print("\n Index (", currentRow ,",",
endCol ,") : ", value, end = "")
result = 1
if (result == 0 and matrix[r][c] < value) :
if (r + 1 <= endRow) :
result = self.search(matrix, r + 1,
endRow, currentCol,
endCol, value)
elif (result == 0) :
if (c - 1 >= currentCol) :
result = self.search(matrix,
currentRow, endRow,
currentCol, c - 1, value)
return result
def searchValue(self, matrix, value) :
row = len(matrix)
col = len(matrix[0])
result = self.search(matrix, 0, row - 1, 0,
col - 1, value)
if (result == 0) :
print("\n None : ", value, end = "")
def main() :
task = Searching()
mat = [
[6, 8, 21, 32, 42],
[9, 12, 25, 33, 45],
[12, 13, 27, 36, 48],
[17, 18, 28, 41, 52],
[27, 30, 46, 49, 62]
]
task.searchValue(mat, 28)
task.searchValue(mat, 48)
if __name__ == "__main__": main()Output
Index ( 3 , 2 ) : 28
Index ( 2 , 4 ) : 48# Ruby Program
# Search in row wise and column wise sorted matrix
class Searching
def search(matrix, currentRow, endRow, currentCol, endCol, value)
r = currentRow + (endRow - currentRow) / 2
c = currentCol + (endCol - currentCol) / 2
if (matrix[r][c] == value)
# Element found on (r,c) location
print("\n Index (", r ,",", c ,") : ", value)
return 1
else
result = 0
if (r != endRow || c != currentCol)
result = self.search(matrix, currentRow,
r, c, endCol, value)
end
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
if (matrix[currentRow][endCol] == value)
print("\n Index (", currentRow ,",",
endCol ,") : ", value)
result = 1
end
end
if (result == 0 && matrix[r][c] < value)
if (r + 1 <= endRow)
result = self.search(matrix, r + 1,
endRow, currentCol, endCol, value)
end
elsif (result == 0)
if (c - 1 >= currentCol)
result = self.search(matrix, currentRow,
endRow, currentCol, c - 1, value)
end
end
return result
end
end
def searchValue(matrix, value)
row = matrix.length
col = matrix[0].length
result = self.search(matrix, 0,
row - 1, 0,
col - 1, value)
if (result == 0)
print("\n None : ", value)
end
end
end
def main()
task = Searching.new()
mat = [
[6, 8, 21, 32, 42],
[9, 12, 25, 33, 45],
[12, 13, 27, 36, 48],
[17, 18, 28, 41, 52],
[27, 30, 46, 49, 62]
]
task.searchValue(mat, 28)
task.searchValue(mat, 48)
end
main()Output
Index (3,2) : 28
Index (2,4) : 48// Scala Program
// Search in row wise and column wise sorted matrix
class Searching()
{
def search(matrix: Array[Array[Int]],
currentRow: Int, endRow: Int, currentCol: Int,
endCol: Int, value: Int): Int = {
var r: Int = currentRow + (endRow - currentRow) / 2;
var c: Int = currentCol + (endCol - currentCol) / 2;
if (matrix(r)(c) == value)
{
// Element found on (r,c) location
print("\n Index (" + r + "," + c + ") : " + value);
return 1;
}
else
{
var result: Int = 0;
if (r != endRow || c != currentCol)
{
result = search(matrix, currentRow, r, c, endCol, value);
}
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
{
if (matrix(currentRow)(endCol) == value)
{
print("\n Index (" + currentRow + "," +
endCol + ") : " + value);
result = 1;
}
}
if (result == 0 && matrix(r)(c) < value)
{
if (r + 1 <= endRow)
{
result = search(matrix, r + 1,
endRow, currentCol, endCol, value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = search(matrix,
currentRow, endRow,
currentCol, c - 1, value);
}
}
return result;
}
}
def searchValue(matrix: Array[Array[Int]], value: Int): Unit = {
var row: Int = matrix.length;
var col: Int = matrix(0).length;
var result: Int = search(matrix, 0, row - 1, 0, col - 1, value);
if (result == 0)
{
print("\n None : " + value);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Searching = new Searching();
var mat: Array[Array[Int]] = Array(
Array(6, 8, 21, 32, 42),
Array(9, 12, 25, 33, 45),
Array(12, 13, 27, 36, 48),
Array(17, 18, 28, 41, 52),
Array(27, 30, 46, 49, 62)
);
task.searchValue(mat, 28);
task.searchValue(mat, 48);
}
}Output
Index (3,2) : 28
Index (2,4) : 48import Foundation;
// Swift 4 Program
// Search in row wise and column wise sorted matrix
class Searching
{
func search(_ matrix: [
[Int]
], _ currentRow: Int,
_ endRow: Int,
_ currentCol: Int,
_ endCol: Int,
_ value: Int) -> Int
{
let r: Int = currentRow + (endRow - currentRow) / 2;
let c: Int = currentCol + (endCol - currentCol) / 2;
if (matrix[r][c] == value)
{
// Element found on (r,c) location
print("\n Index (", r ,",", c ,") : ",
value, terminator: "");
return 1;
}
else
{
var result: Int = 0;
if (r != endRow || c != currentCol)
{
result = self.search(matrix,
currentRow, r, c,
endCol, value);
}
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
{
if (matrix[currentRow][endCol] == value)
{
print("\n Index (", currentRow ,",",
endCol ,") : ", value, terminator: "");
result = 1;
}
}
if (result == 0 && matrix[r][c] < value)
{
if (r + 1 <= endRow)
{
result = self.search(matrix, r + 1,
endRow, currentCol, endCol, value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = self.search(matrix,
currentRow, endRow,
currentCol, c - 1, value);
}
}
return result;
}
}
func searchValue(_ matrix: [
[Int]
], _ value: Int)
{
let row: Int = matrix.count;
let col: Int = matrix[0].count;
let result: Int = self.search(matrix, 0,
row - 1, 0, col - 1, value);
if (result == 0)
{
print("\n None : ", value, terminator: "");
}
}
}
func main()
{
let task: Searching = Searching();
let mat: [
[Int]
] = [
[6, 8, 21, 32, 42],
[9, 12, 25, 33, 45],
[12, 13, 27, 36, 48],
[17, 18, 28, 41, 52],
[27, 30, 46, 49, 62]
];
task.searchValue(mat, 28);
task.searchValue(mat, 48);
}
main();Output
Index ( 3 , 2 ) : 28
Index ( 2 , 4 ) : 48// Kotlin Program
// Search in row wise and column wise sorted matrix
class Searching
{
fun search(matrix: Array < Array < Int >> ,
currentRow: Int, endRow: Int,
currentCol: Int, endCol: Int, value: Int): Int
{
val r: Int = currentRow + (endRow - currentRow) / 2;
val c: Int = currentCol + (endCol - currentCol) / 2;
if (matrix[r][c] == value)
{
// Element found on (r,c) location
print("\n Index (" + r + "," + c + ") : " + value);
return 1;
}
else
{
var result: Int = 0;
if (r != endRow || c != currentCol)
{
result = this.search(matrix,
currentRow, r, c, endCol, value);
}
if (result == 0 && currentRow == endRow &&
currentCol + 1 == endCol)
{
if (matrix[currentRow][endCol] == value)
{
print("\n Index (" + currentRow + "," +
endCol + ") : " + value);
result = 1;
}
}
if (result == 0 && matrix[r][c] < value)
{
if (r + 1 <= endRow)
{
result = this.search(matrix, r + 1,
endRow, currentCol, endCol, value);
}
}
else if (result == 0)
{
if (c - 1 >= currentCol)
{
result = this.search(matrix,
currentRow, endRow,
currentCol, c - 1, value);
}
}
return result;
}
}
fun searchValue(matrix: Array < Array < Int >> , value: Int): Unit
{
val row: Int = matrix.count();
val col: Int = matrix[0].count();
val result: Int = this.search(matrix, 0,
row - 1, 0, col - 1, value);
if (result == 0)
{
print("\n None : " + value);
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Searching = Searching();
val mat: Array < Array < Int >> = arrayOf(
arrayOf(6, 8, 21, 32, 42),
arrayOf(9, 12, 25, 33, 45),
arrayOf(12, 13, 27, 36, 48),
arrayOf(17, 18, 28, 41, 52),
arrayOf(27, 30, 46, 49, 62)
);
task.searchValue(mat, 28);
task.searchValue(mat, 48);
}Output
Index (3,2) : 28
Index (2,4) : 48Time Complexity
The time complexity of this algorithm can be analyzed based on the number of recursive calls. In each recursive
call, we divide the search space into smaller parts. Since we are halving the search space in each recursive call,
the maximum number of recursive calls is proportional to the logarithm of the size of the matrix, resulting in a
time complexity of O(log(max(m, n))), where m is the number of rows and n is
the number of columns in the matrix.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment