[LeetCode] 33. Search in Rotated Sorted Array (C++)

문제

 

https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

 

풀이

 

난이도: Medium 

 

이전 문제 153. Find Minimum in Rotated Sorted Array를 활용해서 해결했는데,

훨씬 깔끔하고 빠른 해결법은 다음 게시글을 참고하자.

[LeetCode]C++ binary search with comments; easy to read and understand

 

 

이전 문제에서는 배열의 시작 위치가 어디인지 O(log n)에 구했으므로 이를 이용하여 이분 탐색으로 target을 찾는 방법으로 문제를 풀었다.

이전에 구한 left의 값은 시작점의 index값이므로 결국 모든 값들이 left만큼 오른쪽으로 이동된 것이 현재 배열의 상태일 것이다.

따라서 이분 탐색을 위한 중간 위치, mid 또한 left만큼 오른쪽으로 이동되었으므로 이를 활용해 mid위치로 범위를 분할하자.

 

단, 기존의 이분 탐색에는 target이 배열에 존재하지 않아서 left가 right보다 커지는 경우를 예외처리를 해주지만

회전된 배열에서는 이미 left가 right보다 큰 경우가 있다.

따라서 회전하지 않은 원본 배열의 left(= 0)와 right(= n-1)도 추가하여 동일하게 범위 분할을 하며, left가 right보다 커지는 경우를 찾아내었다.

 

되는대로 풀다 보니 엉망진창인 코드가 돼버렸네요...

 

코드