Question

A speedy Decrease-and-Conquer search. Use your newly acquired knowledge of “Decrease-and-Conquer” algorithm design strategy to design...

A speedy Decrease-and-Conquer search.

Use your newly acquired knowledge of “Decrease-and-Conquer” algorithm design strategy to design a O( n ) algorithm to search for a given number in an n × n matrix in which every row and every column in this matrix is sorted in increasing order

Write your algorithm as an elegant java method named findElement(int [][] arr, int element) that returns the index of that element in the array as a small int array made of 2 cells only; the first for the row and the second for the column.

if that element is not in the array your method shall return {-1,-1}.

Don't worry there is only one solution to all our test cases.

For example:

Test Input Result
findElement(arr, item);
8 15
9 19

find 9
1 0
findElement(arr, item);
8 15
9 19

find 10
-1 -1
findElement(arr, item);
8 15 19
9 22 26
16 23 30

find 23
2 1

Homework Answers

Answer #1

Java code with findElement() method :

public class DecreaseConquerSearch{
   // Method to find item in matrix arr
       // if found return index of item
       // else return array of {-1,-1}
       private static int[] findElement(int[][] arr, int item)
   {
           int n = arr.length;
  
   int i = 0, j = n - 1;
  
   while (i < n && j >= 0) {
   if (arr[i][j] == item) {
       int[] res = {1,2};
   return res;
   }
   if (arr[i][j] > item)
   j--;
   else
   i++;
   }
  
   int[] res = {-1,-1};
   return res;
   }
  
  
public static void main(String[] args) {
int[][] arr = { {8, 15, 19},
               {9, 22, 26},
               {16, 23, 30}};
int item = 23;
  
int[] res = findElement(arr, item);
  
System.out.print(res[0] + " " + res[1]);
}
}

Output :

1 2

Hope you like it

Any Query? Comment Down!

I have written for you, Please up vote the answer as it encourage us to serve you Best !

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Java question, Please answer everything. Thank you Answer the following questions as briefly (but completely) as...
Java question, Please answer everything. Thank you Answer the following questions as briefly (but completely) as possible: What is a checked exception, and what is an unchecked exception? What is NullPointerException? Which of the following statements (if any) will throw an exception? If no exception is thrown, what is the output? 1: System.out.println( 1 / 0 ); 2: System.out.println( 1.0 / 0 ); Point out the problem in the following code. Does the code throw any exceptions? 1: long value...
Read the attached articles about the proposed merger of Xerox and Fujifilm. Utilizing your knowledge of...
Read the attached articles about the proposed merger of Xerox and Fujifilm. Utilizing your knowledge of external and internal analysis, business and corporate strategy, and corporate governance, please discuss the following questions: 1. What is the corporate strategy behind the merger of Xerox and Fujifilm? 2. Why did Xerox agree to the merger? Is this a good deal for Xerox? Discuss the benefits and challenges they face with the merger. 3. Why did Fujifilm agree to the merger? Discuss the...
Delta airlines case study Global strategy. Describe the current global strategy and provide evidence about how...
Delta airlines case study Global strategy. Describe the current global strategy and provide evidence about how the firms resources incompetencies support the given pressures regarding costs and local responsiveness. Describe entry modes have they usually used, and whether they are appropriate for the given strategy. Any key issues in their global strategy? casestudy: Atlanta, June 17, 2014. Sea of Delta employees and their families swarmed between food trucks, amusement park booths, and entertainment venues that were scattered throughout what would...
1) Describe an example of each of the following that may be found of your kitchen:...
1) Describe an example of each of the following that may be found of your kitchen: Explain how your choice falls into this category, and if there is a chemical name or symbol for it, provide that as well. Provide a photo of your example with your ID card in it. a) a compound b) a heterogeneous mixture c) an element (symbol) Moving to the Caves… Lechuguilla Caves specifically. Check out this picture of crystals of gypsum left behind in...
1. What is an ISP (Integrated Service Provider) for supply chains? (1 point) A. A consultant...
1. What is an ISP (Integrated Service Provider) for supply chains? (1 point) A. A consultant agency which integrates the supply chain for companies B. A 2 PL or a 3PL, but not a 4PL C. A company supplying transportation and warehousing services D. A logistics service company specialized in suppling VAS (value added services) 2. What characterizes a 4 PL? (1 point) A. They are non-asset based and provides integrated services primarily supplied by asset based providers, for example...
QUESTION 1 1. Brianna is trying to increase her chances of being promoted to vice president...
QUESTION 1 1. Brianna is trying to increase her chances of being promoted to vice president by working to build good work relationships with other managers outside her own department. Brianna's behavior should be viewed as dysfunctional politics. functional politics. coercive power. functional influence. 2 points QUESTION 2 1. The Gingerbread Factory has a separate unit that makes their chocolate crunch cookies and another unit that is completely responsible for all operations in producing their ginger snap cookies. The Gingerbread...
Using the model proposed by Lafley and Charan, analyze how Apigee was able to drive innovation....
Using the model proposed by Lafley and Charan, analyze how Apigee was able to drive innovation. case:    W17400 APIGEE: PEOPLE MANAGEMENT PRACTICES AND THE CHALLENGE OF GROWTH Ranjeet Nambudiri, S. Ramnarayan, and Catherine Xavier wrote this case solely to provide material for class discussion. The authors do not intend to illustrate either effective or ineffective handling of a managerial situation. The authors may have disguised certain names and other identifying information to protect confidentiality. This publication may not be...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT