리트코드 - 33. Search in Rotated Sorted Array

홍성진·2023년 2월 26일
0

리트코드 - 33. Search in Rotated Sorted Array

[5,6,7,1,2,3,4]와 같이 오름차순 배열을 임의의 숫자만큼 회전시킨, rotated sorted array가 주어집니다. 이 배열에 주어진 target이 있다면 index를, 없다면 -1을 반환하는 문제입니다. 설명의 편의를 위해 rotated 되기 전 오름차순의 시작점을 시작점이라 하겠습니다.

먼저 배열이 rotate 되어있는지 아닌지 nums[start] < nums[end] 조건문으로 판단합니다. rotate 되어있지 않다면 일반적인 binary search를 실시합니다.

rotate 되어있다면 시작점이 배열의 왼편에 있는지 오른편에 있는지 nums[start] > nums[mid] 조건문으로 판단합니다. 이 조건이 참일때만, 시작점이 배열의 왼편에 있는 것입니다. start부터 mid까지의 오름차순이 깨져있으니까요.

ex)
[6,7,1,2,3,4,5] 에서 6보다 2가 크니까 시작점1이 배열의 왼편에 위치합니다.

이 때 target이 배열의 왼편에 있는지 오른편에 있는지, nums[start] <= target || target <= nums[mid] 조건문으로 판단합니다. 이 조건이 참일때만, 'target'이 배열의 왼편에 있는겁니다.

시작점 오른편에 있을 때도 비슷한 논리로 진행하시면 됩니다.

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


        while (end - start > 1) {
            mid = start + (end - start) / 2;
			
            // not rotated
            if (nums[start] < nums[end]) {

                if (target <= nums[mid]) {
                    end = mid;
                    continue;
                } else {
                    start = mid;
                    continue;
                }
            }
			
            // 시작점이 왼편
            if (nums[start] > nums[mid]) {
                if (target >= nums[start] || target <= nums[mid]) {
                    end = mid;
                    continue;

                } else {
                    start = mid;
                    continue;

                }
			
            // 시작점이 오른편
            } else {
                if (target >= nums[mid] || target <= nums[end]) {
                    start = mid;
                    continue;

                } else {
                    end = mid;
                    continue;

                }

            }

        }

        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }

}

0개의 댓글