Prm 14 : rotatedArraySearch / binarySearch, 경우의 수

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)을 약간 변형하여 해결합니다.

 

---

 

풀이

 

binarySearch를 응용한다.

22번 줄에서 해당 rotated 배열의 가장 왼쪽값과 중간위치의 값을 비교한다

(rotated[left] < rotated[middle])

부분적으로 정렬된 배열이므로, left 위치의 값이 middle 위치의 값보다 작다면 왼쪽은 정렬된 상태이다.

([6,0,1,2,3,4,5]와 같이 정렬되지 않은 경우도 있음.)

또는 왼쪽이 정렬되어 있지 않다면 오른쪽이라도 반드시 정렬되어 있는 상태이다.

 

여기서 왼쪽 정렬된 곳에 target이 위치한다면 right = middle - 1을 통해 자료의 크기를 절반으로 줄이고, 그게 아니라면 오른쪽에서 target을 찾아간다.