Algorithm 13 : rotatedArraySearch

설명

• 부분적으로 오름차순 정렬 된 정수의 배열(rotated)와 정수(target)를 입력받아 target의 인덱스를 리턴해야 한다.
• 부분적으로 정렬된 배열 : 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
• 예시 : [4,5,6,0,1,2,3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬된다.

예시

시간복잡도 O(N)

const rotatedArraySearch = function(rotated, target){
  for(let i=0; i<rotated.length; i++){
    if(rotated[i] === target){
      return i
    }
  }
  return -1
}

생각

1. 이진탐색으로 풀어야 한다는 힌트가 있으니 left,right,middle을 설정하고 while 문을 통해 범위가 완전히 좁혀질 때 까지 반복하자.

시간복잡도 O(logN)

const rotatedArraySearch = (rotated, target) => {
  let left = 0;
  let right = rotated.length -1
  while(left <= right){
    let middle = parseInt((right+left)/2);
    if(rotated[middle] === target){
      return middle
    }
    if(rotated[left] < rotated[middle]){
      if(target < rotated[middle] && rotated[left] <= target){
        right = middle - 1
      } else{
        left = middle +1
      }
    } else{
      if(target <= rotated[right] && rotated[middle] < target) {
        left = middle + 1
      } else{
        right = middle - 1
      }
    }    

깨달은 점

자료구조는 모르겠으면 기본은 일단 외우라 했으니 이건 외워야겠다...