정렬된 배열이 어느 한 기점으로 잘려서 앞뒤가 바뀌어져 있는 상태이다.


(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).


이런 상태에서 특정 숫자를 찾을 때, 해당 배열의 index를 리턴하는 문제이다.

물론 처음부터 끝까지 훑는 식으로 해도 되겠지만... 당연히 이런 문제에서 Time Complexity는 O(N)이 나오면 안된다.



int search(vector<int>& nums, int target)
{
	int nRet = -1;

	int nMin = 0;
	int nMax = nums.size() - 1;
	int nMid = 0;

	while (nMin <= nMax)
	{
		nMid = (nMin + nMax) / 2;

		if (nums[nMid] == target)
		{
			nRet = nMid;
			break;
		}

		if (nums[nMid] > nums[nMax])
		{
			if (target < nums[nMid] && target >= nums[nMin])
				nMax = nMid - 1;
			else
				nMin = nMid + 1;
		}
		else if (nums[nMid] < nums[nMin])
		{
			if (target > nums[nMid] && target <= nums[nMax])
				nMin = nMid + 1;
			else
				nMax = nMid - 1;
		}
		else
		{
			if (target < nums[nMid])
				nMax = nMid - 1;
			else
				nMin = nMid + 1;
		}
	}

	return nRet;
}



무엇을 기준으로 앞뒤를 어떻게 바꿀 것인지에 대해서 되어야 한다.

'Programming > C,C++' 카테고리의 다른 글

[BOJ] 2165. 포도주 시식  (0) 16:00:07
[LeetCode] 34. Search for a Range  (0) 2018.01.26
[LeetCode] 33. Search in Rotated Sorted Array  (0) 2018.01.26
[LeetCode] 22. Generate Parentheses  (0) 2018.01.25
[BOJ] 10844. 쉬운 계단 수  (0) 2018.01.21
[BOJ] 1149. RGB거리  (0) 2018.01.20

+ Recent posts