[Leetcode] 33. Search in Rotated Sorted Array

Identifying the Problem

Rotated된 array에서 target의 index를 리턴한다.

단, target이 array내에 없다면, -1을 리턴한다.

Organizing thoughts

Rotate가 가진 특성은 지난 153번 문제에서 자세히 소개했다.

[Leetcode] 153. Find Minimum in Rotated Sorted Array

오름차순과 내림차순이 가진 특성을 사용하면 쉽게 풀 수있다.

 

1. left랑 mid가 다른동안 반복

2.

<왼쪽 오름차순 오른쪽 오름차순인 경우>

target이 mid 보다 크다 → 오른쪽탐색

target이 mid 보다 작다 → 왼쪽탐색

 

<왼쪽 오름차순 오른쪽 내림차순인 경우>

Left <= target <= mid → 왼쪽탐색

그게 아니라면 → 오른쪽탐색

 

<왼쪽 내림차순 오른쪽 오름차순인 경우>

mid <= target <= Right → 오른쪽탐색

그게 아니라면 → 왼쪽 탐색

 

mid에 해당하는 값과 target이 같으면 return mid

right에 해당하는 값과 target이 같으면 return right

둘다 아니면 target이 존재하지 않는 다는 뜻이므로 -1을 리턴한다.

 

"그게 아니라면" 이 부분이 문제의 핵심인 듯하다.
3 4 5 6 7 1 2  에서 target이 2인 경우
2가 왼쪽 오름차순의 범위에 들어가지 않았기 때문에 오른쪽 탐색을 하도록 한다.
오름차순은 규칙성이 있지만, 내림차순은 규칙성이 없다.
따라서 오름차순범주가 아니므로, 내림차순 범위에 있다고 판단하는 것이다.

Sourcecode

int search(int* nums, int numsSize, int target)
{
	int l = 0;
	int r = numsSize-1;
	int mid = (l+r)/2;
	
	while(l!=mid)
	{
		if(nums[l] < nums[mid] && nums[mid] < nums[r]) //오름차순 오름차순
		{
			if(target > nums[mid]) l = mid;
			else if(target < nums[mid]) r = mid;
			else return mid;
		}
		else if(nums[l] < nums[mid] && nums[mid] > nums[r]) //오름차순 내림차순
		{
			if(nums[l] <= target && target <= nums[mid])	
				r = mid;
			else 
				l = mid;	
		}
		else if(nums[l] > nums[mid] && nums[mid] < nums[r]) //내림차순 오름차순
		{
			if(nums[mid] <= target && target <= nums[r])	
				l = mid;
			else 
				r = mid;	
		}
     	  	 mid = (l+r)/2;
    }
        
		if(nums[mid] == target) return mid;
		else if(nums[r] == target) return r;
		else return -1;
}