[Grind75-LeetCode] Search in Rotated Sorted Array JAVA

반응형

728x90

[Grind75-LeetCode] Search in Rotated Sorted Array - Medium

---

접근

• 이진 탐색 (Binary Search)

---

풀이

배열 내부에 순환이 있는 정렬된 배열에서 특정 원소를 찾아 인덱스를 반환하는 문제이다. 해당 문제는 O(log n)의 시간 복잡도를 가진 알고리즘으로만 통과가 가능하다. 대표적인 탐색 알고리즘에서 범위를 절반씩 줄여가며 진행하는 이진 탐색이 O(log n)으로 이 문제도 이진 탐색을 통해 해결된다. 

 

이 문제의 포인트는 주어지는 배열이 단순하게 정렬된 배열이 아니라는 것이다. 정렬되어 있긴 하지만 내부에 순환점이 존재해

nums = [4,5,6,7,0,1,2]

위와 같은 형태로 0번 인덱스가 제일 작은 값이 아니고 마지막 인덱스가 제일 큰 값이 아닌 상태로 주어진다. 고로 적절하게 범위를 줄여나가는 것이 포인트이다.

    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }

시작 포인터를 0, 끝 포인터를 마지막 인덱스로 하고 루프를 돌리며 범위를 줄이는 과정은 동일하다. 

	    if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else if (nums[mid] <= nums[end]) {
                if (nums[mid] < target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }

구해진 가운데 인덱스의 값과 비교해 정렬된 부분에 따라 진행을 나눠준다. 시작 인덱스의 값이 가운데 인덱스의 값 보다 작은 경우 왼쪽 범위는 올바르게 정렬된 상태로 보고 범위를 줄여나간다. 만약 타겟이 시작 인덱스와 가운데 인덱스 사이에 존재한다면 끝 인덱스를 줄여 해당 범위 탐색을 진행하고 그렇지 않다면 시작 인덱스를 변경하여 반대편을 탐색한다. 왼쪽 부분이 정렬되어 있지 않다면 오른쪽 부분을 탐색하여 왼쪽과 동일한 방법으로 진행해주는데 이는 배열이 순환되어 평범하게 정렬되어 있지는 않지만 순환된 상태에서도 각 부분이 정렬되어 있는 상태로 존재하기 때문에 그 점을 이용하여 탐색이 가능하다. 

---

전체 코드

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else if (nums[mid] <= nums[end]) {
                if (nums[mid] < target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}