[Array, Binary Search] Search in Rotated Sorted Array

 

임의의 pivot index에 의해 rotate된 배열에서 target이 몇번째 위치에 있는지 찾아라.

 

오름차순으로 정렬된 배열은 binary search로 해결하는 것이 일반적이다.

start와 end index를 두고, endIndex가 클때까지 Loop를 돌린다

이 loop는 middle index를 구하고 target이 있다면 해당 값을 리턴하고, target이 더 크다면 startIndex를 우측 반으로, 더 작다면 endIndex를 좌측 반으로 설정한다. 

이는 배열이 오름차순으로 정렬되어 있다는 전제하에 가능한 것이다

 

이 문제도 target이 있다면 리턴해주면 되는데, 문제는 target이 mid가 아닌 경우다

일반적인 binary search 문제대로 오름차순으로 정렬되어 있다면 그냥 쪼개면 되지만 얘는 특정 기준으로 pivot되어있다.

그러나 한번의 pivot역시 나머지 한쪽은 오름차순으로 정렬되어 있음을 뜻한다.

 

이때 nums[left] <= nums[mid]의 조건은 좌측이 오름차순으로 정렬되어 있음을 뜻한다. 

이 경우에 target이 left와 mid사이에 있다면 오른쪽 반을 버리면 된다.

그게 아니라면 이쪽을 버리면 된다.

반대의 경우도 마찬가지이다.