arrays - 搜索不同整数的交换排序数组

Question

上下文:如果有一些 k，不同整数的数组 A[1..n] 称为交换排序， 1 ≤ k ≤ n，因此将 A 的最后 n − k 个元素(按照它们在 A 中出现的顺序)移动到 A 的前 k 个元素生成排序数组。 (请注意，不同整数的排序数组是交换排序的: 取 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 ] 移到前面得到 [6, 5, 4, 3 , 2, 1]，因为降序，所以不考虑交换排序。

我需要一个算法 Search(A, x) 给定一个由不同整数 A 和 an 组成的交换排序数组 整数 x，返回索引 i，1 ≤ i ≤ n，如果存在这样的索引，则 A[i] = x；如果没有则返回 0 索引存在。

该算法应在 O(log n) 时间内运行，其中 n 是 A 的长度。

有谁知道如何解决这个问题？分而治之显然是一种方法，我只是想不出具体步骤。

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)

编辑:

上述算法的复杂度与二分查找相同。

为了正确性，我会做类似的事情:“如果你在任意点拆分一个交换排序数组，至少一个结果数组必须排序，另一个必须(至少)交换排序。如果元素是不在排序数组的范围内，它就不能在那个数组中，如果在范围内，它就不能在排序数组之外。我们继续在排序数组或交换排序数组中搜索。因为任何排序数组都是同样交换排序我们可以再次使用相同的算法。(归纳证明)。”