CODEWITHSUNDEEP
javaarraysalgorithmtime-complexitydivide-and-conquer
Ashis Jena
Ashis Jena

Reputation: 450

Find index of starting point of a sorted cyclic integer array

There are two sorted continuous number array merged in to a single array. Both the arrays had distinct numbers.

ex : 
{1, 2, 3, 4, 5, 6, 7, 8, 9}   and
{10, 11, 12, 13, 14}

int[] resultArr = {10, 11, 12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9};
                                      ^

Algorithm to find the index of the starting point. If we treat it as cyclic array, it will be in sorted order while iterating from the starting point.

In the above example the starting index will be "4"

I've wrote below sample program to solve this, but not happy about the time complexity.

Can someone tell me the time-complexity of the below code and provide a better solution for this problem.

public class FindStartingPoint {

  public static Integer no = null;

  private static void findStartingPoint(int[] arr, int low, int mid, int high) {
    if (no != null)
      return;
    else if (high - low <= 1)
      return;
    else if (arr[mid] > arr[mid + 1]) {
      no = mid + 1;
      return;
    }
    findStartingPoint(arr, low, (low + mid) / 2, mid);
    findStartingPoint(arr, mid, (mid + high) / 2, high);
  }

  public static void main(String[] args) {
    int[] arr = {12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    findStartingPoint(arr, 0, arr.length / 2, arr.length - 1);
    System.out.println(no);
  }
}

Thanks in Advance. :-)

Upvotes: 1

Views: 534

Answers (3)

Phil Anderson
Phil Anderson

Reputation: 3146

You can optimise a bit. Where you have this code...

findStartingPoint(arr, low, (low + mid) / 2, mid);
findStartingPoint(arr, mid, (mid + high) / 2, high);

You actually only need to call one of them not both.

For example, if the number at mid is smaller than the number at low, then you lonly need to call the first one, as the number must be to the left of mid. Otherwise, you only need to call the second one.

That will speed things up a bit.

If this is for an interview then I'd recommend you refactor the code when you have it working so that it's less stateful. I assume you're just playing around getting something working at present though.

Upvotes: 0

biziclop
biziclop

Reputation: 49744

It isn't entirely clear from your description, but if all the numbers to the right of the smallest number are smaller than all of them to the left, the divide-and-conquer algorithm works like this:

  1. Start with your left boundary at the first element and your right boundary at the last.
  2. Take the element that's halfway between the left and right boundaries.
  3. If the middle element is bigger than your left boundary, move the left boundary to the middle element.
  4. If the middle element is smaller than your left boundary, move the right boundary to the middle element.
  5. Repeat from 2 until you've only got 1 element in your range.

Upvotes: 0

Joop Eggen
Joop Eggen

Reputation: 109547

Binary search fits here too. Logarithmic.

public int findStart(int[] numbers) {
    int low = 0;
    int high = numbers.length; // Exclusive
    while (low < high) {
        int middle = (low + high) / 2;
        boolean fitsLow = numbers[low] <= numbers[middle];
        if (fitsLow) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    return low;
}

Upvotes: 4

Related Questions