다른 정수의 교환 정렬 된 배열을 검색

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] 전면에 도착 [6, 5, 4, 3, 2, 1], 순서가 감소하기 때문에 스왑 정렬로 간주되지 않습니다.

스왑 정렬 된 고유 한 정수 A와 정수 x가 주어지면 A [i] = 1이되도록 인덱스 i, 1 ≤ i ≤ n을 반환하는 알고리즘 (Search, A) 그러한 색인이 존재하면 x; 그러한 색인이 없으면 0을 리턴합니다.

알고리즘은 n은 A의 길이 O 시간 (로그 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 :

상기 이진 검색 알고리즘과 동일한 복잡도를 갖는다.

정확함을 위해 "임의의 지점에서 스왑 정렬 된 배열을 분할하면 결과 배열 중 적어도 하나는 정렬되어야하고 다른 배열은 (적어도) 스왑 정렬되어야합니다. 정렬 된 배열 범위를 벗어났습니다. 범위 내에 있으면 정렬 된 배열 외부에있을 수 없습니다. 정렬 된 배열이나 스왑 정렬 된 배열에서 계속 검색합니다. 정렬 된 배열 또한 스왑을 통해 동일한 알고리즘을 다시 사용할 수 있습니다 (유도에 의한 증명). "