一个没有重复值的有序数组，把后半段，放在前半段。比如[4, 5, 6, 1, 2, 3]，请返回最大值的下标。
一般的方法是顺序遍历，复杂度是O(n)。较优的算法是二分搜索。
先查找中点元素，可以分为三种情况。
- arr[m] > arr[m+1] (最大值)
- arr[m] >= arr[p]
- arr[m] < arr[p]
这里注意下第2种情况，为什么不能写成arr[m] > arr[q]呢？
因为有一种特殊情况，[ 1,2]，此时 m = p，所以需要和自己比。
public int find(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
int p = 0;
int q = arr.length - 1;
while (p < q) {
int m = p + (q - p) / 2;
if (arr[m] > arr[m + 1]) {
return m;
}
if (arr[m] >= arr[p]) {
p = m + 1;
} else {
q = m - 1;
}
}
return p; // 当p==q的时候，返回p，这样能处理单调递增的数组
}
下面进入测试阶段。怎样构造这种数组呢？看起来很容易，但其实写得优雅并不简单。我想起来了《编程之美》上的算法：三次swap。
private int[] getArr(final int len) {
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = (i << 1) ;
}
return arr;
}
private void swap(int[] arr, int p, int q) {
while (p < q) {
int x = arr[p];
arr[p] = arr[q];
arr[q] = x;
p++;
q--;
}
}
@Test
public void test() {
final int len = 20;
for (int i = 0; i < len; i++) {
int[] arr = getArr(len);
swap(arr, 0, i);
swap(arr, i + 1, arr.length - 1);
swap(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
Assert.assertTrue(arr[find(arr)] == 38);
}
}
这个方法覆盖了一般情况。特殊情况就是长度是1和2的数组。
这种数组问题，写代码的时候先考虑一般情况，然后再用特殊情况微调。
需要注意的是，数组中不能存在重复元素，否则算法会失效
当arr[p] = arr[m] = arr[q]的时候，无法分辨最大值在左边，还是右边。
对下一题也有如此限制，因为此题是下一题的基础。
另外对于测试用例，并不是数组越长越好。数组越长，有些特殊情况反而不容易造出来。
