java - 查找已排序循环整数数组的起点索引

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

提前致谢。 :-)

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