Future Group, Mumbai Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes
I assume that Sorted Matrix means sorted across each row and each column, instead of sorted as per BFS.
For that case, this will not work. Try to find 4 in the following matrix:
1 2 3 4
2 5 6 7
3 6 7 8
5 7 8 9
Correct Solution:
#Start from Top-Right position.
#If it's value is greater than the search_value, move down and discard the current row.
#If it's value is lesser than search_value, move left and discard the current column.
#Else, you have found your search_value.
#Repeat until you find the search_value or reach the bottom-left.
Maximum moves: N towards left + N towards down.
So Complexity: O(N).
1. Use a modified version of binary search for first column (Lets name is as c1):
- Harmit January 14, 2012it return the position of the number if found
else return i such that c1[i]< searchItem < c1[i+1]
2. Now search for the searchItem if not found in the first step in ith row of the main array using binary search