알고리즘 17 : rotatedArraySearch

rotatedArraySearch

문제

부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

• 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
• 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.

입력

인자 1 : rotated

• number 타입을 요소로 갖는 배열
• rotated[i]는 정수

인자 2 : target

• number 타입의 정수

출력

• number 타입을 리턴해야 합니다.

주의사항

• rotated에 중복된 요소는 없습니다.
• target이 없는 경우, -1을 리턴해야 합니다.

입출력 예시

let output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2);
console.log(output); // --> 5

output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100);
console.log(output); // --> -1

Advanced

• 단순히 처음부터 끝까지 찾아보는 방법(O(N)) 대신 다른 방법(O(logN))을 탐구해 보세요.

힌트

• 이진 탐색(binary search)을 약간 변형하여 해결합니다.

 

코드

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  let left = 0;
  let right = rotated.length-1;

  while(left<=right){
    let mid = parseInt((left+right)/2)
    if(rotated[mid]===target)return mid
    
    //중앙선을 왼쪽이 넘었는지 오른쪽이 넘었는지부터 본다.
    //오른쪽이 중앙선을 넘었을때
    if(rotated[mid]<rotated[left]){
      if(target<=rotated[right] && target>rotated[mid]){
        left = mid+1;
      }else{ right = mid-1;}
    }
    
    //왼쪽이 중앙을 넘었을때
    else{
      if(target>=rotated[left] && target<rotated[mid]){
        right = mid-1;
      }else{
        left = mid+1;
      }
    }
  
  }return -1
};

 

설명

왼쪽 영역이 중앙을 넘었을 경우만 설명한다.

나머지 경우도 사고방식은 같다.

left = mid + 1 하는 경우의 수는 2가지(보라,주황)이고, right = mid - 1 하는 경우의 수(파랑)는 1가지 이다.

 

그러니 편리하게 파랑색의 조건이 아닌 나머지는 다 else로 처리한다.

else{
	//파란색 부분
	  if(target>=rotated[left] && target<rotated[mid]){
        right = mid-1;
      }
    //보라색부분, 주황색부분
      else{
        left = mid+1;
      }
    }