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

indexOf了解下

有序隊(duì)列，直接使用二分法，處理就是把隊(duì)列切半遞歸查找。

如果不允許用indexOf，其實(shí)這個(gè)是一個(gè)很有意思的題，可能很多人沒(méi)有注意到這個(gè)是一個(gè)循環(huán)遞增數(shù)組，意思是在數(shù)組中有一個(gè)最小值，其左邊是最大值??！如果能很快定位這個(gè)值的位置，整個(gè)序列就變成了有序數(shù)組了，用折半查找就會(huì)比較快了，但如果沒(méi)有定位，則折半查找是有一些問(wèn)題的。

具體實(shí)現(xiàn)

function MyindexOf(k, arr, l, h) {
    if(l==h && k!=arr[l]) return -1;
    if(arr[l]==k) return l;
    if(arr[h]==k) return h;
    if(l>h){
       let t=h;
           h=l;
           l=t;
    }
    let m=Math.ceil((l + h) / 2);
    if(arr[m]==k) return m;
    if(m==h||m==l) return -1;//表明中間沒(méi)有空位了，也排除了a[m]==a[l]和a[m]==a[h]的情況
    if(arr[l]<arr[h]){ //普通二分法查找
        if(arr[h]<k) return -1;
        if(arr[l]>k) return -1;
        if(arr[m]>k) return MyindexOf(k,arr,l+1,m-1);
        return MyindexOf(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]) return MyindexOf(k,arr,m+1,h-1);//右
            return MyindexOf(k,arr,l+1,m-1);//左
        }else{//k>arr[m]
            if(arr[m]>arr[l]) return MyindexOf(k,arr,l+1,m-1);//普左
            return -1; //arr[m]<arr[l]，悖論了
        }  
    }else{ //k<arr[l]
        if(k>arr[h]){
            return -1;//不可能存在于arr[l]，arr[h]區(qū)間中
        }else{//k<arr[h]
            if(k>arr[m]){
                return MyindexOf(k,arr,m+1，h-1);//其實(shí)包含了arr[m]>arr[h]與arr[m]<arr[h]兩種情況
            }else{ //k<arr[m]
                if(arr[m]>arr[h]){
                    return MyindexOf(k,arr,m+1,h-1);
                }else{
                    if(arr[m]<arr[h]) return MyindexOf(k,arr,l+1,m-1);
                }
            }
        }
    
    }
    return -1;
}

這就是循環(huán)遍歷去判斷啊?；蛘哂脭?shù)組的 indexOf 方法。

var arr = [5, 8, 9, 10, 1, 3, 4];
var k = 3;

function getK(k) {
    for(var i = 0; i < arr.length; i++) {
        if(k === arr[i]) {
            return i
        }
    }
    return -1
}

var kIndex = getK(k);
console.log('kIndex:', kIndex)

下面這個(gè)是二分查找的方式，可以減少?gòu)?fù)雜度。

var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
    if (low <= high) {
        if (arr[low] == find) {
            return low;
        }
        if (arr[high] == find) {
            return high;
        }
        var mid = Math.ceil((high + low) / 2);
        if (arr[mid] == find) {
            return mid;
        } else if (arr[mid] > find) {
            return binary(find, arr, low, mid - 1);
        } else {
            return binary(find, arr, mid + 1, high);
        }
    }
    return -1;
}
binary(15, Arr, 0, Arr.length - 1);