How can I search for a value in a column-wise sorted array in linear time O(n)?
I need to write a function that takes in a column-wise sorted 2d array, and returns true if a specified value is in the array.
Example of a column-wise sorted array
int[][] m = {
{1, 2, 3},
{4, 6, 5},
{8, 10, 9}
};
How can I solve this problem in linear time O(n)?
Considering the array is sorted column wise we can visit all the columns to find the target element. Suppose there are N columns in worst case scenario we have to visit all the columns and we have to search for the element across M rows for each of these.
Since the matrix is sorted col wise we could do search in log(M) - leading to N*log(M) worst case time complexity.
But if you meant O(n) as N elements of col then we should think to optimize more.