JavaScript Algorithm - rotatedArraySearch

 

문제설명 : 부분적으로 정렬된 배열(rotated)과 찾고자 하는 값이 있는 target를 입력 받은 뒤 

target의 인덱스를 반환해야합니다.  다음 조건들을 확인한 뒤 문제를 풀어봅시다~

 

입력

인자 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

let output2 = rotatedArraySearch([10, 11, 12, 3, 6, 7, 8, 9], 11);
console.log(output2); // --> 1

Advanced

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

 

 

풀이코드 설명

const rotatedArraySearch = function (rotated, target) {
  //이진탐색과 달리 right에 배열길이 -1 값을 저장
  let left = 0,
    right = rotated.length - 1;

  while (left <= right) {
    let middle = parseInt((right + left) / 2);

	//middle 인덱스와 target이 같으면 middle 인덱스를 반환, 리턴
    if (rotated[middle] === target) {
      return middle;
    }

    if (rotated[left] < rotated[middle]) {
      // 왼쪽 절반이 정렬되어 있는 상태
      // left인덱스 <= target < middle 인덱스
      if ( rotated[left] <= target && target < rotated[middle]) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    } else {
      // 오른쪽 절반이 정렬되어 있는 상태
      // middle 인덱스 <= target < right 인덱스
      if (  rotated[middle] < target && target <= rotated[right]) {
        left = middle + 1;
      } else {
        right = middle - 1;
      }
    }
  }

  return -1;
};