fork(1) download
copy 
  1. class Go {
  2.  
  3. public static void main(String args[]){ 
  4.   int[][] dataSets = { { 42 },
  5.                        { 42, 64 },
  6.                        { 64, 42 },
  7.                        { 1, 2, 3 },
  8.                        { 2, 3, 1 },
  9.                        { 3, 2, 1 },
  10.                        { 4, 5, 6, 7, 1, 2, 3 },
  11.                        { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
  12.                        { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
  13.                        { 9, 1, 2, 3, 4, 5, 6, 7, 8 }
  14.                      };
  15.  
  16.   System.out.println("Max Values:");
  17.   for(int i=0; i< dataSets.length; ++i)
  18.     System.out.println(findLargestValueInSemiSortedArray(dataSets[i]));
  19.  
  20.   boolean failed = false;
  21.   try { findLargestValueInSemiSortedArray(null);       failed = true; }
  22.   catch(IllegalArgumentException e) { ; }
  23.   try { findLargestValueInSemiSortedArray(new int[0]); failed = true; }
  24.   catch(IllegalArgumentException e) { ; }
  25.   if(!failed)
  26.     System.out.println("Correctly Rejected Illegal Values");
  27. }
  28.  
  29. public static int findLargestValueInSemiSortedArray(int arr[]) {
  30.   if(arr==null || arr.length==0)
  31.     throw new IllegalArgumentException();
  32.  
  33.   int hi  = arr.length; /* exclusive upper bound */
  34.   int low = 0;          /* inclusive lower bound */
  35.   int mid = low/2 + hi/2;
  36.   while(low < hi) {
  37.     if(isPivotIndex(arr,mid))
  38.       return arr[mid];
  39.     if(arr[hi-1] < arr[mid])
  40.       low = mid + 1;
  41.     else
  42.       hi  = mid;
  43.     mid = low/2 + hi/2;
  44.   }
  45.   /* Array was actually sorted, either ascending or descending    */
  46.   /* Note that return this covers corner cases of arr.length <= 3 */
  47.   return max(arr[0], arr[arr.length-1]); 
  48. }
  49.  
  50. public static int max(final int a, final int b) {
  51.   return (a > b) ? a : b;
  52. }
  53.  
  54. public static boolean isPivotIndex(final int[] arr, final int index) {
  55.   int b = arr[index];
  56.   int a = (index > 0) ?            arr[index-1] : Integer.MAX_VALUE;
  57.   int c = (index < arr.length-1) ? arr[index+1] : Integer.MAX_VALUE;
  58.   return a <= b && b > c;
  59. }
  60.  
  61. }
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max Values:
42
64
64
3
3
3
7
9
9
9
Correctly Rejected Illegal Values
https://ideone.com/UZLz20
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!