문제

int형 배열 nums가 주어진다. nums는 초기에는 정렬되어있으며 pivot만큼 왼쪽으로 회전한 배열이다. nums = [1, 2, 3, 4, 5, 6, 7], pivot = 3일 때 nums = [4, 5, 6, 7, 1, 2, 3]이 된다.

문제는 이렇게 만들어진 nums 배열에서 target의 인덱스를 찾는 문제이다. 단 시간복잡도가 $O(log N)$을 만족해야한다.

첫번째 풀이

pivot을 찾아서 배열의 두 부분으로 나누어 찾는 것이었다. pivot을 기준으로 배열을 두 부분으로 나누면 각 배열은 오름차순으로 정렬되어있는 배열이기 때문에 이진탐색으로 target의 인덱스를 구할 수 있다.

pivot 또한 이진탐색으로 그 위치를 구한다. 그 이유는 문제에서 시간복잡도 $O(log N)$을 요구했기 때문이다. pivot의 탐색 기준은 중간(mid)의 값이 오른쪽(right) 값보다 작으면 right를 mid 값으로 업데이트 한다. 즉 배열에서 최솟값의 위치를 찾는 것과 동일하다.

배열의 최솟값의 위치가 pivot + 1번째 인덱스가 된다.

따라서 시간복잡도는 $O(logN)$을 만족시켰으며 공간복잡도는 $O(1)$로 구현할 수 있었다.

class Solution {
    public int search(int[] nums, int target) {
		int pivot = getPivotIndex(nums);

		int targetIndex = findTargetIndex(nums, target, 0, pivot - 1);
		if (targetIndex != -1) {
			return targetIndex;
		}

		return findTargetIndex(nums, target, pivot, nums.length - 1);
	}

	public int getPivotIndex(int[] nums) {
		int left = 0, right = nums.length - 1;
		while (left < right) {
			int mid = (left + right) / 2;

			if (nums[mid] > nums[right]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return left;
	}

	public int findTargetIndex(int[] nums, int target, int left, int right) {
		while (left <= right) {
			int mid = (left + right) / 2;

			if (nums[mid] == target) {
				return mid;
			} else if (nums[mid] > target) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return -1;
	}
}

Solution 참고

이진 탐색으로 풀었고 공간복잡도 또한 $O(1)$로 가장 좋은 방법이라 생각하였고 더 개선할 방법을 생각하지 못하였다. 그래서 Solution을 참고 했는데 기본은 이진 탐색과 동일하지만 한 번의 이진 탐색으로 풀이한 풀이가 많았다. 아직 정확히 이해하지 못해 이해가 되면 추가해야겠다.