Searching a swap-sorted array of distinct integers

Question

Context: An array A[1..n] of distinct integers is called swap-sorted if there is some k, 1 ≤ k ≤ n, so that moving the last n − k elements of A (in the order in which they appear in A) before the first k elements of A results in a sorted array. (Note that a sorted array of distinct integers is swap-sorted: take k = n.) Also, the swap-sorted array must be in INCREASING ORDER.

Example: [ 4, 5, 6, 1, 2, 3] => move [1, 2, 3 ] to the front to [1, 2, 3, 4, 5, 6], which is considered swap-sorted. (increasing order)

Non-example: [ 3, 2, 1, 6 , 5, 4 ] => move [6, 5, 4 ] to the front to get [6, 5, 4, 3, 2, 1], not considered swap-sorted since decreasing order.

I need an algorithm Search(A, x) which, given a swap-sorted array of distinct integers A and an integer x, returns an index i, 1 ≤ i ≤ n, such that A[i] = x if such an index exists; and returns 0 if no such index exists.

The algorithm should run in O(log n) time, where n is the length of A.

Does anyone know how to approach this? Divide and conquer certainly seems like one way to do it, I just can't think of the steps.

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:

The above algorithm has the same complexity as binary search.

For correctness I'd do something like: "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)."