[알고리즘] rotatedArraySearch

문제 설명

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

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

제한사항

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

알고리즘

1. rotated 된 기준점(pivot, mid )을 찾는다.
2. 왼쪽과 오른쪽으로 정렬된 부분으로 나뉘어 탐색을 시작한다.
3. array[mid] 의 값이 왼쪽정렬(시작점 left ) 값보다 크면 왼쪽 정렬 탐색을 시작한다.
   3-1.왼쪽정렬( left )부터 기준점 사이에 target이 포함하면 right = mid - 1
   3-2.위 경우가 아니면, left = mid + 1
4. array[mid] 의 값이 왼쪽정렬( left ) 값보다 작으면 오른쪽 정렬 탐색을 시작한다.
   4-1.기준점부터 오른쪽정렬(끝점 right ) 사이에 target이 포함된다면 left = mid + 1
   4-2.위 경우가 아니면, right = mid - 1
5. while 의 조건에 도달할 때까지 left 와 right 값이 변화함에 따라 mid (기준점)이 바뀌며 범위를 좁혀나간다.
6. array[mid] 와 target 이 동일하면 인덱스 값인 mid 를 반환한다.
7. 그렇지 않을 경우, target이 존재하지 않으므로 ' -1 '을 반환한다.

구현

function rotatedArray(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      return mid;
    }

    if (array[left] <= array[mid]) {
      if (array[left] <= target && target <= array[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (array[mid] <= target && target <= array[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

다른사람 풀이

시간복잡도가 O(n)인 풀이

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

시간복잡도가 O(log n)인 풀이

const rotatedArraySearch = function (rotated, target) {
  let left = 0,
    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;
      }
    }
  }

  return -1;
};