一道二分法的算法题

Question

1.下面数组是从1到n连续的数组(n>2)，从中间折断交换顺序后，用二分法找到数组中 1 的索引。数组: [n-x+1, n-x+2, ..., n - 1, n, 1, 2, 3, 4, 5, ..., n-x]示例: [7,8,9,10,11,12,13,14,15,1,2,3,4,5,6]我的答案：step1:先对数组进行升序排序例：n=15,x=9,arr=[7,8,9,10,11,12,13,14,15,1,2,3,4,5,6]arr.slice(n-x-1,x).concat(arr.slice(0,n-x-1))step2:二分法查找function getLocation(arr, key, startNum, endNum) {  if (arr == null) return -1;  var middleNum = Math.floor((startNum + endNum) / 2);  console.log("中间值：" + middleNum);  if (startNum < endNum) {    if (key == arr[middleNum]) {      return middleNum + 1;    } else if (key < arr[middleNum]) {      return getLocation(arr, key, startNum, middleNum);    } else {      return getLocation(arr, key, middleNum, endNum);    }  } else if (startNum == endNum) {    return startNum;  } else {    return -1;  }}console.log(getLocation([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 10, 1, 15))面试官说不行，不能先拼，直接二分法查找？？二分法不在一个有序的数列里怎么使用？感觉是被搞了么

Answer 1

排完序数组第一个不就是1吗还二分干啥？而且，有排序的功夫，复杂度o(nlogn），你扫一遍数组不都扫出来了么？所以先排序再二分查找的点在哪里？

不对，你的答案有个奇怪的东西！！！！你都知道切割位置是 9 了，还从 9 的位置处 slice 开，再交换位置 concat 再二分查找？ What？ 什么鬼，你要是都知道要从 9 的地方切开数组，那答案就是 9+1 啊！！！！

所以说先审题。

1. 数组是一个1到n的有序数组从中间折断再拼接的，所以说数组本身前后两部分都是有序的

2. 要查找的是1的位置，说白了就是查找数组折断再拼接的位置

解：若 i < j < k 则升序数组中 arr[i] < arr[j] < arr[k] 。如果 i、k 是二分中的 low 和 high, j 是中值，不等式哪边不成立，就说明哪边不是连续递升，拼接点就在哪端。

Answer 2

排序后还要找？不是直接在第一个了么？所以你的答案有什么意义！