Search in Rotated Sorted Array

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

Search in Rotated Sorted Array - LeetCode

 

배열에서 타겟의 값을 찾는 문제이다. 특이점으로는 배열이 정렬되어있으나 해당 정렬은 왼쪽으로 회전 되어있을 수 있다는 점이다.

 

사실 문제 요구 사항으로 O(log n) 시간 복잡도를 요구하나 단순 for문(시간 복자도 O(n))으로 찾아도 문제가 통과된다. 하지만 알고리즘 연습을 위해 푸는 문제이니 정석적인 방법으로 풀었다.
O(log n)의 시간 복잡도를 요구한다는 것은 이진 탐색 알고리즘을 사용하라는 것으로 이해하면 된다.

 

단 조건이 회전된 배열일 수 있으므로 조건을 더 세분화 하여야 한다.
우선 이진탐색을 위해 left, right, mid 를 선정한 이후 조건을 세분화하여 left, right 의 값을 변화시키며 이진 탐색을 하여 해결하였다. 조건 선정에 자꾸 실패하여 꽤나 고생했다. 아래는 최종적으로 통과한 코드이다.

 

mid를 중심으로 왼쪽 또는 오른쪽은 신뢰할 수 있게 정렬 되어있다는 점을 이용하여 조건을 나누었다.

public class Solution {  
    public int search(int[] nums, int target) {  
        int left = 0;  
        int right = nums.length - 1;  
        while(left <= right){  
            int mid = (left + right) / 2;  
            int s = nums[left];  
            int e = nums[right];  
            int cur = nums[mid];  
  
            if(target == cur){  
                return mid;  
            }  
  
            if(cur >= s){  
                // 왼쪽이 정렬되어있을 경우  
                if(target > cur){  
                    left = mid + 1;  
                }else if(target >= s){  
                    right = mid - 1;  
                }else{  
                    left = mid + 1;  
                }  
            }else{  
                // 오른쪽이 정렬되어있을 경우  
                if(target < cur){  
                    right = mid - 1;  
                }else if(target <= e){  
                    left = mid + 1;  
                }else{  
                    right = mid - 1;  
                }  
            }  
        }  
  
        return -1;  
    }  
}