INTERVIEW QUESTIONS ALGORITHM DETAILS

Question: How do you apply Binary Search on 2D array supposed you have 2D array with integers sorted both horizontally and vertically. If you find any occurrence of the value you are looking for you return true else false. What is the complexity?

For example the 2D array could look like the following

1 4 5 6
2 5 7 9

Answer: search diagonally.

diag 1 = 1
diag2 = 2,4
….

for example
given the number 7 we take the bounds of each diagonal and check wether the number will fall in that range else move farward.
here diagonal selection is sequential but the number search is binary.

search diagonally.

diag 1 = 1
diag2 = 2,4
….

for example
given the number 7 we take the bounds of each diagonal and check wether the number will fall in that range else move farward.
here diagonal selection is sequential but the number search is binary. Source: CoolInterview.com

sort on the last column
suppose
n*n matrix
low= 0;
high =n-1;
while ( low!=high )
{
mid = floor [( low + high )/2];
if(a[mid][n-1]==item)
return
if(a[mid][n-1]>item)
high = mid;
if(a[mid][n-1]<item)
low= mid+1;
}
apply binary search on 1d array left
Source: CoolInterview.com

If you have the better answer, then send it to us. We will display your answer after the approval.

Rules to Post Answers in CoolInterview.com:-

• There should not be any Spelling Mistakes.
• There should not be any Gramatical Errors.
• Answers must not contain any bad words.
• Answers should not be the repeat of same answer, already approved.
• Answer should be complete in itself.

Name :*
Email Id :*
Answer :*
Verification Code	Not readable? Load New Code
Enter the above shown code: *
	Inform me about updated answers to this question