Search in Rotated Sorted Array - LeetCode

Problem

1. input: 정수가 든 배열 nums, 정수 target
2. output: nums에서 target의 인덱스 리턴, 없을 경우 -1 리턴
3. nums는 최초 오르차순 정렬된 상태에서 0번 이상rotate된 상태
4. 시간 복잡도 제한 O(log n)
   • 1 <= nums.length <= 5000
   • 10^4 <= nums[i] <= 10^4
   • All values of nums are unique.
   • nums is an ascending array that is possibly rotated.
   • 10^4 <= target <= 10^4

Idea

1. 시간 복잡도 제한 O(log n)이므로 이분탐색으로 target의 인덱스를 찾으면 된다. 특이사항은 배열이 오름차순 정렬된 이후 rotate되었으므로, 탐색 구역 조건분기만 잘해주면 된다.

Solution

1. 이분탐색

   • 회전이 안된 경우

     일반 이분탐색 방법과 동일

   • 회전이 된 경우

     • target이 mid보다 작은 경우
       • 회전 X 구간 (ex 1,2,3,4,5) if (start ≤ target < mid) 아랫구간 탐색
       • 회전 된 구간 (ex 4,5,1,2,3) if (start ≤ target && start > mid) 아랫구간 탐색
       • 둘다 아닌 경우 윗구간 탐색
     • target이 mid보다 큰 경우
     • 회전 X 구간 (ex 1,2,3,4,5) if (mid ≤ target < end) 윗구간 탐색
     • 회전 된 구간 (ex 4,5,1,2,3) if (mid ≤ target && mid > end) 윗구간 탐색
     • 둘다 아닌 경우 아랫구간 탐색

   class Solution {
       fun search(nums: IntArray, target: Int): Int {
           fun checkInIncrease(from: Int, value: Int, to: Int): Boolean {
               // 1 2 3 4 5 -> target = 4
               return nums[from] <= value && value <= nums[to]
           }
           fun checkInRotate(from: Int, value: Int, to: Int): Boolean {
               // 4 5 1 2 3 -> target = 5 or 2
               return (nums[from] <= value && nums[from] > nums[to]) || (nums[to] >= value && nums[from] > nums[to])
           }
           var start = 0
           var end = nums.size - 1
           var mid = (start + end) / 2
           while (start <= end && nums[mid] != target) {
               if (nums[start] < nums[end]) { // rotate X
                   if (nums[mid] > target) end = mid - 1 else start = mid + 1
               } else { // rotate
                   if (nums[mid] > target) {
                       if (checkInIncrease(start, target, mid) || checkInRotate(start, target, mid)) end = mid - 1 else start = mid + 1
                   } else {
                       if (checkInIncrease(mid, target, end) || checkInRotate(mid, target, end)) start = mid + 1 else end = mid - 1
                   }
               }
               mid = (start + end) / 2
           }
           return if (nums[mid] == target) mid else -1
       }
   }
   

   시간 복잡도: 이분탐색 = log n

   

Point

1. 이분탐색에서 조건만 조금 신경쓰면 됨