(a) Given an array A of n distinct integer elements with the following property: The first...

 

Transcribed Image Text:

(a) Given an array A of n distinct integer elements with the following property: The first k elements (0 < k < n-1) are in strictly increasing sequence followed by the strictly decreasing sequence. Example: A = {1, 3, 4, 5, 7, 14, 11, 7, 2, -4, -8). It monotonically increases from 1 to 14, then decreases from 14 to -8 Implement a sub-linear running time complexity program in Java that, given an array with the previous property, determines whether a given integer is in the array. (b) The input is an N by N matrix of nonnegative integers. Each individual row is a decreasing sequence from left to right. Each individual column is a decreasing sequence from top to bottom. Implement in Java a linear running time algorithm that decides if a number x is in the matrix. Please include in the header of your Java program (using comments) the main ideas of your algorithm. Example of the 4 x 4 matrix: /26 22 17 10\ 19 16 12 7 12 10 7 4 5 4 2 1 Important Notes: You must add the main method in your program in order to test your implementation. (a) Given an array A of n distinct integer elements with the following property: The first k elements (0 < k < n-1) are in strictly increasing sequence followed by the strictly decreasing sequence. Example: A = {1, 3, 4, 5, 7, 14, 11, 7, 2, -4, -8). It monotonically increases from 1 to 14, then decreases from 14 to -8 Implement a sub-linear running time complexity program in Java that, given an array with the previous property, determines whether a given integer is in the array. (b) The input is an N by N matrix of nonnegative integers. Each individual row is a decreasing sequence from left to right. Each individual column is a decreasing sequence from top to bottom. Implement in Java a linear running time algorithm that decides if a number x is in the matrix. Please include in the header of your Java program (using comments) the main ideas of your algorithm. Example of the 4 x 4 matrix: /26 22 17 10\ 19 16 12 7 12 10 7 4 5 4 2 1 Important Notes: You must add the main method in your program in order to test your implementation.

Answer rating: 100% (QA)

This program first need to find the peak element using binary search then it performs binary search ... View the full answer