Suppose A is a matrix with n rows and n columns. Further suppose that A is sorte
ID: 3572371 • Letter: S
Question
Suppose A is a matrix with n rows and n columns. Further suppose that A is sorted both by rows and by columns i.e, within any row. the elements are increasing from left to right, and within any column, the elements are increasing from top to bottom. We want to determine if a k is one of the entries in A. The obvious way of doing this would look at all n^2 entries of A, but you how to do letter i.e. come up with a more efficient algorithm. Give a clear description of your algorithm for the above problem. Show how your algorithm works on two examples, one where the answer is YES, another where the answer is NO. Do a worst case time analysis (use big O notation) of your algorithm.Explanation / Answer
The following algorithm is implemented based on Binary search to find the element in the n*n matrix.
Algorithm:
Start
Get the size of the matrix and read the values in increasing order.
Procedure for searching element:
let low=0, high=n
Read the element to be searched, s
While (low<high)
Begin
Mid=(low+high)/2
If (s==a[i][mid])
Print “The element found at position” I, mid
Else if (s<a[i][mid])
High=mid
Else
Low=mid+1
End
End
End while
3. End
Example:
Given Matrix is
12 30 33
37 40 45
48 50 55
Enter the number to be searched:
50
The number 50 is at position :(3,2)
Given Matrix is
12 30 33
37 40 45
48 50 55
Enter the number to be searched:
60
The number 60 not found.
Complexity Analysis:
best case will be when the element is found at the first search i.e. at the mid of the matrix i.e. by Mid=(low+high)/2
Whereas
The worst case will happen when the whole matrix is searched and the element is found at the last position or element not found at all.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.