異なる整数のスワップソートされた配列を検索

Question

コンテキスト：配列A [1..nの】異なる整数のスワップソート一部kが存在する場合に呼び出される、 1≤k個の≤nを、その結果移動 の最初のk個の要素がソートされた配列になる前に、Aの最後のn - k個の要素（Aに表示される順序で）。 （別々の整数のソートされた配列はスワップソートされていることに注意してください。 はk = nを取る）また、スワップソートされた配列はINCREASING ORDERである必要があります。

例：[4,5,6,1,2,3] => [1、2、3]を[1,2,3,4,5,6]に前に移動する。スワップソートと見なされます。 （昇順）

非例：[3、2、1、6、5、4] => [6、5、4を得るためにフロント[4、6、5]を移動し、 3,2,1]、順序が減少するのでスワップソートされていないとみなされます。

スワップソートされた異なる整数Aの配列と 整数xが与えられた場合、A [i] = 1となるインデックスi、1≤i≤nを返すアルゴリズムSearch（A、x）そのようなインデックスが存在する場合はxそのような インデックスが存在しない場合は0を返します。

アルゴリズムは、nはAの長さであるO（log n）時間で実行する必要があり

誰もがこれをアプローチする方法を知っていますか？分裂と征服は確かにそれを行う一つの方法のように思える、私はちょうどステップを考えることはできません。

Answer 1

function findHelper(leftIndex, rightIndex,arr, el){ 

    var left=arr[leftIndex] 
    var right=arr[rightIndex] 
    var centerIndex=Math.round((leftIndex+rightIndex)/2) 
    var center=arr[centerIndex] 
    console.log(leftIndex+":"+rightIndex) 
    if(right==el){ 
    return rightIndex 
    } 
    if(left==el){ 
    return leftIndex 
    } 
    if(center==el){ 
    return centerIndex 
    } 
    if(Math.abs(leftIndex-rightIndex)<=2){ // no element found 
    return 0; 
    } 

    if(left<center){ //left to center are sorted 
    if(left<el && el<center){ 
     return findHelper (leftIndex, centerIndex, arr, el) 
    } 
    else{ 
     return findHelper (centerIndex, rightIndex, arr, el) 
    } 
    } 
     else if(center<right){//center to right are sorted 
     if(center<el && el<right){ 
      return findHelper (centerIndex, rightIndex, arr, el) 
     } 
    else{ 
     return findHelper (leftIndex, centerIndex, arr, el) 
    } 
    } 

} 

function find(el, arr){ 
    return findHelper(0, arr.length-1, arr,el)+1 
} 

// some testcases 
console.log(find(1, [1,2,5,8,11,22])==1) 
console.log(find(2, [1,2,5,8,11,22])==2) 
console.log(find(5, [1,2,5,8,11,22])==3) 
console.log(find(8, [1,2,5,8,11,22])==4) 
console.log(find(11, [1,2,5,8,11,22])==5) 
console.log(find(22, [1,2,5,8,11,22])==6) 

console.log(find(11, [11,22, 1,2,5,8])==1) 
console.log(find(22, [11,22, 1,2,5,8])==2) 
console.log(find(1, [11,22, 1,2,5,8])==3) 
console.log(find(2, [11,22, 1,2,5,8])==4) 
console.log(find(5, [11,22, 1,2,5,8])==5) 
console.log(find(8, [11,22, 1,2,5,8])==6) 

EDIT：

上記のアルゴリズムは、バイナリサーチと同じ複雑さを有します。

「スワップソートされた配列を任意の点で分割すると、少なくとも1つの結果の配列をソートしなければならず、もう1つは（少なくとも）スワップソートする必要があります。がソートされた配列の範囲内にない場合、ソートされた配列の範囲外にあることはできません。ソートされた配列またはスワップのソートされた配列のいずれかを検索し続けます。同じアルゴリズムをもう一度使うこともできます（誘導による証明）。