首頁猿問在從某個(gè)元素開始，循環(huán)遞增的數(shù)組中...

在從某個(gè)元素開始，循環(huán)遞增的數(shù)組中，查找k的位置？

JavaScript

炎炎設(shè)計(jì) 2019-05-20 17:08:42

5,8,9,10,1,3,4givenk,findpositionofkinarray,-1在上述特點(diǎn)（從某個(gè)元素開始，循環(huán)遞增）的數(shù)組中，查找k的位置，其中，k為任意的實(shí)數(shù)，若找到則返回下標(biāo)，否則返回-1，寫代碼實(shí)現(xiàn)

查看完整描述

2 回答

牛魔王的故事

TA貢獻(xiàn)1830條經(jīng)驗(yàn) 獲得超3個(gè)贊

如果不允許用indexOf，其實(shí)這個(gè)是一個(gè)很有意思的題，可能很多人沒有注意到這個(gè)是一個(gè)循環(huán)遞增數(shù)組，意思是在數(shù)組中有一個(gè)最小值，其左邊是最大值??！如果能很快定位這個(gè)值的位置，整個(gè)序列就變成了有序數(shù)組了，用折半查找就會(huì)比較快了，但如果沒有定位，則折半查找是有一些問題的。具體實(shí)現(xiàn)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);}//下面是特殊二分法查找了，因?yàn)椴豢赡苡衋rr[l]==arr[h]了，所以不用判斷arr[l]>arr[h]了，下面默認(rèn)是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]區(qū)間中}else{//kif(k>arr[m]){returnMyindexOf(k,arr,m+1，h-1);//其實(shí)包含了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;}

反對回復(fù) 2019-05-20

慕的地6264312

TA貢獻(xiàn)1817條經(jīng)驗(yàn) 獲得超6個(gè)贊

這就是循環(huán)遍歷去判斷啊?；蛘哂脭?shù)組的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)下面這個(gè)是二分查找的方式，可以減少復(fù)雜度。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);