In this project. you are given a unimodal array of n integer and your task is to
ID: 3676508 • Letter: I
Question
In this project. you are given a unimodal array of n integer and your task is to find the maximum integer in the array in theta(logn) time. An unimodal array of integers is an array with entries that monotonically increase up to the maximum integer value and then monotonically decrease for the rest of the array. For example: (2, 5, 8, 9, 12, 15, 21, 17, 10, 4) is a unimodal array of ten integers that increase from 2 ... 21 and then decrease from 21 ... 4. The integer 21 is the maximum value of the integer in the array. You could use a modified version of the binary search algorithm discussed in Module 2 to design and implement an algorithm for the above unimimodal array maximum element problem.Explanation / Answer
import java.util.Arrays;
public class main{
public static void main(String[] args) {
int[] E = {12, 34, 51, 75, 202, 4324};
System.out.println(Arrays.toString(E));
System.out.println(Chapter03.binarySearch(E, 51));
int[] unimodalArray = {2, 5, 8, 9, 12, 15, 21, 17, 10, 4};
System.out.println(Arrays.toString(unimodalArray));
System.out.println(Chapter03.unimodalSearch(unimodalArray));
}
/* IN: A, an array, and target, the element to be searched for
* OUT: the index of A where target is found (-1 if not found)
*/
public static int binarySearch(int[] A, int target) {
int lowerBound = 0;
int upperBound = A.length - 1;
while (lowerBound <= upperBound) {
int mid = lowerBound + (int) (lowerBound + upperBound) / 2;
if (A[mid] > target) {
upperBound = mid;
} else if (A[mid] < target) {
lowerBound = mid;
} else {
return mid;
}
}
return -1;
}
/* IN: A, an unimodal (increasing sequence followed by decreasing sequence) array
* OUT: index of the maximum element in A
*/
public static int unimodalSearch(int[] A) {
int lowerBound = 0;
int upperBound = A.length-1;
while (lowerBound < upperBound) {
int mid = (int) (lowerBound + upperBound) / 2;
if (A[mid] < A[mid+1]) {
lowerBound = mid+1;
} else if (A[mid] > A[mid+1]) {
upperBound = mid;
}
}
return lowerBound;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.