[LeetCode] 33. Search in Rotated Sorted Array

문제 설명

문제 풀이

시간 복잡도 : O(logN) / 공간 복잡도 : O(N)

기본적인 방식은 Binary Search 방식을 사용하되 mid = (left+right)/2 인덱스 기준으로 왼쪽 혹은 오른쪽은 완전히 정렬되어 있다는 점을 이용하여 분기문을 달리하여 풀이하였다.

소스 코드 (JAVA)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = (right + left) / 2;
            
            //찾으면 결과 리턴 
            if (nums[mid] == target)
                return mid;
            
            //왼쪽 부분이 완전히 정렬된 경우 
            else if (nums[left] <= nums[mid]) {
                
                // 오른쪽 선택 
                if (nums[mid] < target || nums[left] > target) {
                    left = mid + 1;
                    
                // 왼쪽 선택 
                } else {
                    right = mid - 1;
                }
                
            //오른쪽 부분이 완전히 정렬된 경우 
            } else {
                // 왼쪽 선택 
                if (target < nums[mid] || target > nums[right]) {
                    right = mid - 1;
                
                // 오른쪽 선택 
                } else {
                    left = mid + 1;
                }
 
            }
                
        }
        return -1;
    }
}