Thursday 13 August 2015

Find minimum element in rotated array (Assume array is rotated clock wise)

import java.util.Objects;

public class Findmin {
 public static int getMin(int arr[]) {
  Objects.nonNull(arr);

  if (arr.length < 3) {
   if (arr[0] > arr[1])
    return arr[1];
   return arr[0];
  }

  int low = 0, high = arr.length - 1;
  int mid;

  while (low < high) {
   mid = (low + high) / 2;

   if (arr[mid] > arr[high])
    low = mid;
   else if (arr[mid] < arr[low])
    high = mid;
  }

  return arr[low];
 }
}
Following is the junit test case for above program
import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class FindminTest {

 @Test
 public void test1() {
  int arr1[] = { 5, 6, 7, 1, 2, 3, 4 };
  int arr2[] = { 5, 6, 7, 2, 3, 4 };
  int arr3[] = { 5, 6, 7, 3, 4 };
  int arr4[] = { 5, 6, 7, 4 };
  int arr5[] = { 159, 165, 200, 245, 56, 78, 85, 91, 109, 123, 145 };
  int arr6[] = { 159, 165, 200, 245, 342, 456, 56, 78, 85, 91, 109, 123,
    145 };
  int arr7[] = { 159, 165, 200, 245, 342, 7, 7, 7, 98, 100, 120 };
  int arr8[] = { 12, 13, 14, 5, 5, 5, 6, 7, 8 };

  assertEquals(Findmin.getMin(arr1), 1);
  assertEquals(Findmin.getMin(arr2), 2);
  assertEquals(Findmin.getMin(arr3), 3);
  assertEquals(Findmin.getMin(arr4), 4);
  assertEquals(Findmin.getMin(arr5), 56);
  assertEquals(Findmin.getMin(arr6), 56);
  assertEquals(Findmin.getMin(arr7), 7);
  assertEquals(Findmin.getMin(arr8), 5);
 }

}


No comments:

Post a Comment