一道二分法的算法题

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到n的有序数组从中间折断再拼接的，所以说数组本身前后两部分都是有序的要查找的是1的位置，说白了就是查找数组折断再拼接的位置解：若 i < j < k 则升序数组中 arr[i] < arr[j] < arr[k] 。如果 i、k 是二分中的 low 和 high, j 是中值，不等式哪边不成立，就说明哪边不是连续递升，拼接点就在哪端。

Answer 2

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