In this project, you are given a unimodal array of n integers and your task is t

Question

In this project, you are given a unimodal array of n integers and your task is to find the maximum integer in the array in (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 unimodal .may maximum element problem. Documentation (in both the bard copy report mid video): Provide a pseudo code of a (logn) algorithm for the above problem and explain its working. Explain your actual code and execute it with the following three types of unimodal arrays of size at least 10 integers: The maximum integer is the first element in the array: this is basically an array of integers sorted in descending/reverse order The maximum integer is the last element in the array: this is basically an array of integers sorted in increasing/ascending order The array has a sequence of monotonically increasing sequence of at least three integers followed by a monotonically decreasing sequence of at least three integers

Explanation / Answer

We can modify the standard Binary Search algorithm for the given type of arrays.
i) If the mid element is greater than both of its adjacent elements, then mid is the maximum.
ii) If mid element is greater than its next element and smaller than the previous element then maximum lies on left side of mid. Example array: {3, 50, 10, 9, 7, 6}
iii) If mid element is smaller than its next element and greater than the previous element then maximum lies on right side of mid. Example array: {2, 4, 6, 8, 10, 3, 1}

You can test with different array values.

public class MaxInArray {
  
   public static int findMaximum(int arr[], int low, int high)
   {

       /* Base Case: Only one element is present in arr[low..high]*/
       if (low == high)
         return arr[low];

       /* If there are two elements and first is greater then
          the first element is maximum */
       if ((high == low + 1) && arr[low] >= arr[high])
          return arr[low];

       /* If there are two elements and second is greater then
          the second element is maximum */
       if ((high == low + 1) && arr[low] < arr[high])
          return arr[high];

       int mid = (low + high)/2;   /*low + (high - low)/2;*/

       /* If we reach a point where arr[mid] is greater than both of
         its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
         is the maximum element*/
       if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
          return arr[mid];

       /* If arr[mid] is greater than the next element and smaller than the previous
        element then maximum lies on left side of mid */
       if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
         return findMaximum(arr, low, mid-1);
       else // when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
         return findMaximum(arr, mid + 1, high);
   }
  
   public static void main(String[] args) {
       int arr[] = {1, 3, 50, 10, 9, 7, 6};
      
       System.out.println("The maximum element is "+ findMaximum(arr, 0, arr.length));
   }

}

Time Complexity: O(Logn)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.