Efficient Search in Sorted Matrices

Introduction

In computer science, a matrix is a two-dimensional array of numbers, symbols, or expressions arranged in rows and columns. A sorted matrix is a matrix in which the rows and columns are sorted in ascending order. In this challenge, we are given a sorted matrix and we need to search for a specific item in it.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/sorting_searching("`Sorting Searching`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/sorting_searching -.-> lab-268881{{"`Search Sorted Matrix`"}} python/conditional_statements -.-> lab-268881{{"`Search Sorted Matrix`"}} python/while_loops -.-> lab-268881{{"`Search Sorted Matrix`"}} python/lists -.-> lab-268881{{"`Search Sorted Matrix`"}} python/tuples -.-> lab-268881{{"`Search Sorted Matrix`"}} python/function_definition -.-> lab-268881{{"`Search Sorted Matrix`"}} python/classes_objects -.-> lab-268881{{"`Search Sorted Matrix`"}} python/encapsulation -.-> lab-268881{{"`Search Sorted Matrix`"}} python/raising_exceptions -.-> lab-268881{{"`Search Sorted Matrix`"}} python/build_in_functions -.-> lab-268881{{"`Search Sorted Matrix`"}} end

Search Sorted Matrix

Problem

Given a sorted matrix, we need to search for a specific item in it. The matrix is sorted in such a way that the items in each row and column are sorted in ascending order. The matrix is not necessarily a square matrix. We need to return the position of the item in the matrix as a tuple (row, col) if it is found, otherwise, we need to return None.

Requirements

To solve this problem, we need to make the following assumptions:

The items in each row of the matrix are sorted in ascending order.
The items in each column of the matrix are sorted in ascending order.
The matrix is not jagged, i.e., it is a rectangle.
The sorting order is ascending.
The matrix is not necessarily a square matrix.
The output is a tuple (row, col).
The item we are searching for may or may not be in the matrix.
The inputs may or may not be valid.
The solution should fit in memory.

Example Usage

We can use the following test cases to verify our solution:

If the input is None, the function should raise an exception.
If the item is found in the matrix, the function should return its position as a tuple (row, col).
If the item is not found in the matrix, the function should return None.

Summary

In this challenge, we learned how to search for a specific item in a sorted matrix. We made some assumptions about the matrix and the item we are searching for, and we provided some test cases to verify our solution.

Search Sorted Matrix

Introduction

Skills Graph

Search Sorted Matrix

Problem

Requirements

Example Usage

Summary

Other Algorithm Tutorials you may like