알고리즘 9 : 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 : 여기에 코드를 작성합니다.
    //rotated = [9, 10, 11,12,13,14,15, 4, 6, 8], target = 14// return 5
    let last = rotated.length-1
    let first = 0
    let mid = parseInt((first+last)/2)
    
    
    while(first<=last){
      
      mid = parseInt((first+last)/2)
      if(rotated[mid]===target)return mid

     if(rotated[mid]<rotated[first]){//오른쪽이 더 길거나 같을때
     
        if(target<=rotated[last] && target>rotated[mid]){
          first = mid+ 1
        }
        else {
          last = mid - 1
        }
    
      }

         
      //rotated[mid]=13
      else{//왼쪽이 더 길다
        if(target>=rotated[first] && target<rotated[mid]){
          last = mid-1
        }
        else {
          first = mid+1
        }
       
      }
     
    }
    return -1
  };

 

설명

처음에는 힌트를 이용하지 않고 나만의 방식대로 했다.

 

  let max = Math.max(...rotated) // 최대값 구하기
  //이후 최대값을 기준으로 배열을 반으로 자름

하지만 지금 생각해보니 이게 이미 배열을 전체 순회하는 과정이었다.

단순히 처음부터 끝까지 찾아보는 방법인 O(N)을 사용하지 않고 진행할수록 계산량이 줄어드는 O(logN)을 사용해야 했다.

 

이진탐색같은 방법을 사용해야 했다.

 

때문에 아래 코드처럼 점점 배열의 범위를 줄여나가는 방법을 사용했다.

while(first<=last){
      
      mid = parseInt((first+last)/2)
      if(rotated[mid]===target)return mid

     if(rotated[mid]<rotated[first]){//오른쪽이 더 길거나 같을때
     
        if(target<=rotated[last] && target>rotated[mid]){
          first = mid+ 1
        }
        else {
          last = mid - 1
        }
    
      }

         
      //rotated[mid]=13
      else{//왼쪽이 더 길다
        if(target>=rotated[first] && target<rotated[mid]){
          last = mid-1
        }
        else {
          first = mid+1
        }
       
      }
     
    }return -1