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