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

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

Answer 2

从你的描述中不是很清楚，但是如果最小数字右边的所有数字都小于左边的所有数字，分而治之算法是这样工作的：

从第一个元素的左边界开始，最后一个元素的右边界开始。
取左右边界中间的元素。
如果中间元素大于你的左边界，将左边界移到中间元素。
如果中间元素小于你的左边界，将右边界移到中间元素。
从 2 开始重复，直到范围内只有 1 个元素。

Answer 3

你可以优化一下。你在哪里有这个代码...

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

实际上你只需要调用其中一个而不是两个。

比如mid的号码小于low的号码，那么你只需要拨打第一个，因为号码必须在[=的左边11=]。否则，你只需要调用第二个即可。

这会加快速度。

如果这是为了面试，那么我建议您在代码运行时对其进行重构，以减少它的状态。我假设你目前只是在玩弄一些东西。

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

Find index of starting point of a sorted cyclic integer array

java

arrays

algorithm

time-complexity

divide-and-conquer