Tuesday 30 June 2015

Rotation point in sorted Array

Array A is sorted in ascending order, and rotated at some random point. Write a program to figure out this random point.

As per problem statement, array A is sorted in ascending order, and rotated (Assume elements are rotated clock wise) at some random point, so input looks like

For the input,
A = [56, 78, 85, 91, 109, 123, 145, 159, 165, 200, 245]

If Array A is rotated clockwise 4 times, then it becomes like following.

A = [159, 165, 200, 245, 56, 78, 85, 91, 109, 123, 145]

In the above case, rotation point is 56, it is at index 4.

In given problem, elements in array are sorted, so we can utilize this.

Logic is simple, find middle element and compare it with elements in low and high positions, decide on which way (left/right) you should travel.

If A[mid] <= A[high])  we have to traverse left.

If(A[mid] > A[low]) we have to traverse right.

public class FindRotationPoint {

 public static int getRotationPoint(int arr[]) {

  /* Check null condition */
  if (arr == null) {
   throw new NullPointerException();
  }

  if (arr.length <= 2) {
   return 0;
  }

  int low = 0, high = arr.length - 1;
  int mid = (low + high) / 2;

  while (low < high) {
   if (arr[mid] <= arr[high]) {
    high = mid;
   } else if (arr[mid] > arr[low]) {
    low = mid;
   }
   mid = (low + high) / 2;
  }
  return high;
 }
}


import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class FindRotationPointTest {

 @Test(expected = NullPointerException.class)
 public void testNullCondition() {
  FindRotationPoint.getRotationPoint(null);
 }

 @Test
 public void testSingleElement() {
  int arr[] = { 5 };
  assertEquals(0, FindRotationPoint.getRotationPoint(arr));
 }

 @Test
 public void testDoubleElement() {
  int arr[] = { 5, 6 };
  assertEquals(0, FindRotationPoint.getRotationPoint(arr));
 }

 @Test
 public void testNormal_1() {
  int arr[] = { 159, 165, 200, 245, 56, 78, 85, 91, 109, 123, 145 };
  assertEquals(4, FindRotationPoint.getRotationPoint(arr));
 }

 @Test
 public void testNormal_2() {
  int arr[] = { 159, 165, 200, 245, 342, 456, 56, 78, 85, 91, 109, 123,
    145 };
  assertEquals(6, FindRotationPoint.getRotationPoint(arr));
 }

 @Test
 public void testNormal_3() {
  int arr[] = { 1, 2, 3, 4, 5 };
  assertEquals(0, FindRotationPoint.getRotationPoint(arr));
 }

 @Test
 public void testduplicates_1() {
  int arr[] = { 159, 165, 200, 245, 342, 7, 7, 7, 98, 100, 120 };
  assertEquals(5, FindRotationPoint.getRotationPoint(arr));
 }

 @Test
 public void testduplicates_2() {
  int arr[] = { 5, 5, 5, 5, 5, 5 };
  assertEquals(0, FindRotationPoint.getRotationPoint(arr));
 }

 @Test
 public void testduplicates_3() {
  int arr[] = { 12, 13, 14, 5, 5, 5, 6, 7, 8 };
  assertEquals(3, FindRotationPoint.getRotationPoint(arr));
 }

}


No comments:

Post a Comment