How to search in a Row-wise and Column-wise Sorted 2D Array in Python

In this tutorial, we’re going to learn how to search in a row-wise and column-wise sorted two-dimensional array in Python.

But before going forward, we need to understand how to implement an efficient algorithm to do the same. The first challenge we’re going to face with the usual linear searching method is the time complexity which is O(n²). We need to reduce our time complexity and simplify our code.

Search an element in a row-wise & column-wise sorted 2D array in Python

def search(arr,n,element):
        i=0;
        j=n-1;
        while(i<n and j>=0):
                if(arr[i][j]==element):
                        print("Element found at row no. ",(i+1)," column no. ",(j+1));
                        return 1;
                elif(arr[i][j]>element):
                        j=j-1;
                else:
                        i=i+1;
        print("Element was not found in the array");
        return 0;

arr=[[1,2,3],[4,5,6],[7,8,9]];
print("Displaying the array:");
print(arr);
element=int(input("Please enter a number that you want to search in the array:\n"));
search(arr,3,element);

Here, inside the ‘search()‘ function, we’re using two loop variables ‘i‘ and ‘j‘ for row count and column count respectively. Next, we’re using the while loop to search each individual element present in the array. If the condition satisfies, we’re printing the element. At the end of this loop, if our searched element isn’t found in the array then we’re displaying a message of the same.

Output:

Displaying the array:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Please enter a number that you want to search in the array:
1
Element found at row no. 1 column no. 1