Wednesday, 29 July 2015

Find start position of second sub array

An array contains two sub- sorted arrays. Write a program to find starting point of second array.

For example, for an array {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11} Starting index of second array is 6.
We can solve this problem, by using binary search kind of approach.
import java.util.Objects;

public class SecondArray {
 public static int getSecondArrayPosition(int arr[]) {
  Objects.nonNull(arr);
  int low = 0, high = arr.length - 1;
  int middle;

  while (low < high) {
   middle = (low + high) / 2;
   if ((middle-1 > -1) && arr[middle] < arr[middle - 1])
    return middle;
   else if (((middle+1) < arr.length) && arr[middle] > arr[middle + 1])
    return middle + 1;
   else if (arr[middle] > arr[low] && arr[middle] < arr[middle + 1])
    low = middle + 1;
   else
    high = middle - 1;
  }
  return -1;
 }
}


Following is the junit test case for above program.

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class SecondArrayTest {

 @Test
 public void test1() {
  int arr1[] = { 1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 };
  int arr2[] = { 1, 4, 5, 7, 8, 9, 10, 2, 3, 6, 10, 11 };
  int arr3[] = { 1, 4, 5, 7, 8, 9, 10, 11, 2, 3, 6, 10, 11 };
  int arr4[] = { 1, 2, 3, 4, 5, 6 };
  int arr5[] = { 1, 5, 4, 3, 2, 1 };
  int arr6[] = { 1 };
  int arr7[] = { 1, 2 };
  int arr8[] = { 1, -1 };
  int arr9[] = {5, 6, 7, 8, 5};

  assertEquals(SecondArray.getSecondArrayPosition(arr1), 6);
  assertEquals(SecondArray.getSecondArrayPosition(arr2), 7);
  assertEquals(SecondArray.getSecondArrayPosition(arr3), 8);
  assertEquals(SecondArray.getSecondArrayPosition(arr4), -1);
  assertEquals(SecondArray.getSecondArrayPosition(arr5), 2);
  assertEquals(SecondArray.getSecondArrayPosition(arr6), -1);
  assertEquals(SecondArray.getSecondArrayPosition(arr7), -1);
  assertEquals(SecondArray.getSecondArrayPosition(arr8), 1);
  assertEquals(SecondArray.getSecondArrayPosition(arr9), 4);
 }

}




No comments:

Post a Comment