알고리즘rotatedArraySearch

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;
};

ex) const rotated = [8, 9, 10, 1, 2, 3, 4, 5, 6, 7]; ,target = 5

배열은 [1, 2, 3, 4, 5, 6, 7, 8, 9] 라는 배열을 오른쪽으로 회전시켜서 만들어진 배열이다.

즉, 배열의 처음 3개의 원소가 배열의 끝으로 이동한 것이다. 이런 형태의 배열에서 특정 값을 찾는 문제를 이진 탐색 알고리즘을 사용하여 해결할 수 있다.

 

우선 이진 탐색 알고리즘에서는 배열의 중간값을 찾아서, 이 값이 찾으려는 값보다 작은지 큰지를 비교한다.

따라서 중간값을 구하기 위해 left, right 변수를 이용해서 탐색 범위를 지정한다.

이진 탐색 알고리즘에서는 일반적으로 left = 0, right = 배열의 길이 - 1 로 초기화한다.

그리고 while문을 사용해서 left와 right가 만날 때까지 반복한다.

 

let left = 0,
    right = rotatedArray.length - 1;

while (left <= right) {
  // 이진 탐색 알고리즘 수행
}

 

여기서는 회전된 배열의 특성을 고려해서 추가적인 처리가 필요하다.

배열을 반으로 나누어서 왼쪽 절반이 정렬되어 있는지, 오른쪽 절반이 정렬되어 있는지를 판단

 

예를 들어, 배열의 중간값이 2이고, 왼쪽 절반이 정렬되어 있는 경우를 생각해보겠다.

이 경우에는 중간값이 왼쪽 절반의 최솟값보다 큰 경우이다.

이는 왼쪽 절반이 정렬되어 있다는 의미이므로, 찾으려는 값이 중간값보다 작으면 왼쪽 절반에 위치할 가능성이 높다.

따라서, 탐색 범위를 중간값의 왼쪽으로 좁혀준다.

 

    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;
      }
    }

이렇게 탐색 범위를 좁혀가면서 찾으려는 값과 일치하는 원소를 찾거나, 탐색 범위가 없어질 때까지 반복한다.

 마지막으로 찾으려는 값이 없으면 -1을 반환

 

rotated =[8, 9, 10, 1, 2, 3, 4, 5, 6, 7];에서

초기 상태에서 탐색 범위는 배열의 처음 인덱스 0과 마지막 인덱스 9로 지정된다.

중간 인덱스 4에 위치한 값 2가 중간값이다.

오른쪽 절반이 정렬되어있는 상태와 

target이 5이므로  

left = middle + 1 = 5, right = 9

middle = parseInt((right + left) / 2) = 7

rotated[middle] = 5

 

rotated[middle] = 5와 target이 같으므로 

middle=7로 7로 return된다.