在从某个元素开始，循环递增的数组中，查找k的位置？

Question

5,8,9,10,1,3,4
given k, find position of k in array, -1
在上述特点（从某个元素开始，循环递增）的数组中，查找k的位置，其中，k为任意的实数，若找到则返回下标，否则返回-1，写代码实现

Answer 1

如果不允许用indexOf，其实这个是一个很有意思的题，可能很多人没有注意到这个是一个循环递增数组，意思是在数组中有一个最小值，其左边是最大值！！如果能很快定位这个值的位置，整个序列就变成了有序数组了，用折半查找就会比较快了，但如果没有定位，则折半查找是有一些问题的。具体实现function MyindexOf(k, arr, l, h) {&nbsp; &nbsp; if(l==h && k!=arr[l]) return -1;&nbsp; &nbsp; if(arr[l]==k) return l;&nbsp; &nbsp; if(arr[h]==k) return h;&nbsp; &nbsp; if(l>h){&nbsp; &nbsp; &nbsp; &nbsp;let t=h;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;h=l;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l=t;&nbsp; &nbsp; }&nbsp; &nbsp; let m=Math.ceil((l + h) / 2);&nbsp; &nbsp; if(arr[m]==k) return m;&nbsp; &nbsp; if(m==h||m==l) return -1;//表明中间没有空位了，也排除了a[m]==a[l]和a[m]==a[h]的情况&nbsp; &nbsp; if(arr[l]<arr[h]){ //普通二分法查找&nbsp; &nbsp; &nbsp; &nbsp; if(arr[h]<k) return -1;&nbsp; &nbsp; &nbsp; &nbsp; if(arr[l]>k) return -1;&nbsp; &nbsp; &nbsp; &nbsp; if(arr[m]>k) return MyindexOf(k,arr,l+1,m-1);&nbsp; &nbsp; &nbsp; &nbsp; return MyindexOf(k,arr,m+1,h-1);&nbsp; &nbsp; }&nbsp; &nbsp; //下面是特殊二分法查找了，因为不可能有arr[l]==arr[h]了，所以不用判断arr[l]>arr[h]了，下面默认是arr[l]>arr[h]&nbsp; &nbsp; if(k>arr[l]) {&nbsp; &nbsp; &nbsp; &nbsp; if(k>arr[m]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(arr[m]>arr[l]) return MyindexOf(k,arr,m+1,h-1);//右&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return MyindexOf(k,arr,l+1,m-1);//左&nbsp; &nbsp; &nbsp; &nbsp; }else{//k>arr[m]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(arr[m]>arr[l]) return MyindexOf(k,arr,l+1,m-1);//普左&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return -1; //arr[m]<arr[l]，悖论了&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp;&nbsp; &nbsp; }else{ //k<arr[l]&nbsp; &nbsp; &nbsp; &nbsp; if(k>arr[h]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return -1;//不可能存在于arr[l]，arr[h]区间中&nbsp; &nbsp; &nbsp; &nbsp; }else{//k<arr[h]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(k>arr[m]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return MyindexOf(k,arr,m+1，h-1);//其实包含了arr[m]>arr[h]与arr[m]<arr[h]两种情况&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else{ //k<arr[m]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(arr[m]>arr[h]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return MyindexOf(k,arr,m+1,h-1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(arr[m]<arr[h]) return MyindexOf(k,arr,l+1,m-1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; return -1;}

Answer 2

这就是循环遍历去判断啊。或者用数组的 indexOf 方法。var arr = [5, 8, 9, 10, 1, 3, 4];var k = 3;function getK(k) {&nbsp; &nbsp; for(var i = 0; i < arr.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if(k === arr[i]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1}var kIndex = getK(k);console.log('kIndex:', kIndex)下面这个是二分查找的方式，可以减少复杂度。var Arr = [3, 5, 6, 7, 9, 12, 15];function binary(find, arr, low, high) {&nbsp; &nbsp; if (low <= high) {&nbsp; &nbsp; &nbsp; &nbsp; if (arr[low] == find) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return low;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if (arr[high] == find) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return high;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; var mid = Math.ceil((high + low) / 2);&nbsp; &nbsp; &nbsp; &nbsp; if (arr[mid] == find) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return mid;&nbsp; &nbsp; &nbsp; &nbsp; } else if (arr[mid] > find) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return binary(find, arr, low, mid - 1);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return binary(find, arr, mid + 1, high);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1;}binary(15, Arr, 0, Arr.length - 1);

Answer 3

indexOf了解下

Answer 4

有序队列，直接使用二分法，处理就是把队列切半递归查找。