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

Question

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

Answer 1

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

Answer 2

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