搜索不同整數的交換排序數組

上下文：不同整數的數組A [1..n]被稱爲交換排序如果有一些k， 1≤k≤n，以便移動A的最後n-k個元素（按它們在A中出現的順序）在A的前k個元素之前產生排序數組。（請注意，不同整數的排序陣列是交換排序的：需要k = n。）另外，交換排序的陣列必須位於增加順序。搜索不同整數的交換排序數組

示例：[4,5,6,1,2,3] =>將[1,2,3]向前移動到[1,2,3,4,5,6]，其中被認爲是交換排序的。（升序）

非例如：[3，2，1，6,5，4] =>移動[6，5,4]，將前面得到[6,5，4， 3，2，1]，不考慮自降序以來的交換排序。我需要一個算法搜索（A，x）其中給定一個交換排序的不同整數數組A和一個整數x，返回一個索引i，1≤i≤n，使得A [i] = x如果存在這樣的指數;並且如果沒有這樣的索引存在，則返回0。

這個算法應該在O（log n）的時間，其中n是A的長度運行

有誰知道如何處理呢？分而治之當然似乎是一種做法，我只是想不到這些步驟。

來源

2017-10-14 Brainpower2049

你能提供一些例子嗎？ – Zabuza

[在旋轉的有序數組中搜索數字]的可能重複（https://stackoverflow.com/questions/1878769/searching-a-number-in-a-rotated-sorted-array） –

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)

編輯：

上述算法具有相同的複雜性，因爲二進制搜索。爲了正確性，我會這樣做：「如果在任意點處分割交換排序數組，至少必須對一個結果數組進行排序，而另一個必須（至少）交換排序。如果元素不在有序數組的範圍內，它不能在數組中，如果它在範圍內，它不能在有序數組之外，我們繼續在有序數組或交換有序數組中搜索。也是交換排序，我們可以再次使用相同的算法（通過歸納證明）。「

來源

2017-10-15 00:01:01 user2887596

搜索不同整數的交換排序數組

回答

相關問題