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

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，returns 索引 i，1 ≤ i ≤ n，如果存在这样的索引，则 A[i] = x； returns 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)

编辑：

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

为了正确起见，我会这样做："If you split a swap sorted array at a arbitrary point at least one of the resulting arrays must be sorted and the other must be (at least) swap sorted. If the element is not in the range of the sorted array it can not be in that array, if it is in range it can not be outside of the sorted array. We continue searching either in the sorted or in the swap sorted array. Since any sorted array is also swap sorted we can use the same algorithm again. (Proof by induction)."

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

Searching a swap-sorted array of distinct integers

arrays

algorithm

search

computer-science

divide-and-conquer