Найти индекс начальной точки сортированного циклического целочисленного массива

Question

Существует два отсортированных массива непрерывных чисел, объединенные в один массив. Оба массива имели различные числа.

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}; 
            ^

Алгоритм определения индекса начальной точки. Если мы будем рассматривать его как циклический массив, он будет отсортирован в порядке, итерации с начальной точки.

В приведенном выше примере начальный индекс будет «4»

Я написал ниже пример программы, чтобы решить эту проблему, но не рад временной сложности.

Может ли кто-нибудь сказать мне сложность во времени приведенного ниже кода и обеспечить лучшее решение этой проблемы.

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. :-)

Answer 1

Бинарный поиск подходит и здесь. Логарифмическая.

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; 
} 

Answer 2

Это не совсем ясно из вашего описания, но если все цифры справа от наименьшего числа меньше, чем все из них слева, алгоритм разделяй и властвуй работает следующим образом:

1. Начните с левой границы в первом элементе и на правой границе в конце.
2. Возьмите элемент, расположенный на полпути между левой и правой границами.
3. Если средний элемент больше левой границы, переместите левую границу в средний элемент.
4. Если средний элемент меньше вашей левой границы, переместите правую границу к среднему элементу.
5. Повторите с 2 до тех пор, пока у вас не будет только 1 элемент в вашем диапазоне.

Answer 3

Вы можете немного оптимизировать. Где у вас есть этот код ...

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

Вам на самом деле нужно позвонить только одному из них не для обоих.

Например, если число на mid меньше, чем число в low, то вам Lonly нужно назвать первый один, так как это число должно быть слева от mid. В противном случае вам нужно только вызвать второй.

Это ускорит работу.

Если это для собеседования, я бы рекомендовал вам реорганизовать код, когда вы его работаете, чтобы он был менее сдержанным. Я предполагаю, что вы сейчас просто играете, когда что-то работаете.