https://leetcode.com/problems/search-in-rotated-sorted-array/description/
회전된 정렬된 숫자배열이 주어질 때, target 값을 찾고 있다면 그 index를 반환하라.
Binary search의 종합 선물세트 문제.
우선 회전된 rotated index를 찾는다.
이후 target 값을 검색하되, 실제 access해야 할 index는 (index+rotateIndex) % arraySize 이다.
코드
더보기
int searchMinIdxBS(vector<int>& nums, int left, int right)
{
if (left > right) return -1;
// 1, 2, 3, 4, 5
//
// 5, 1, 2, 3, 4
// 4, 5, 1, 2, 3
//
// 3, 4, 5, 1, 2
// 2, 3, 4, 5, 1
int mid = left + (right - left) / 2;
if (nums[left]<=nums[mid] && nums[mid]<=nums[right])
return left;
else if (nums[left] >= nums[mid] && nums[mid] <= nums[right])
{
if (mid > 0 && nums[mid - 1] >= nums[mid]) return mid;
return searchMinIdxBS(nums, left, mid - 1);
}
else
{
if (right > 0 && nums[right - 1] >= nums[right]) return right;
return searchMinIdxBS(nums, mid+1, right);
}
}
int searchRotatedTargetIdxBS(vector<int>& nums, int left, int right, int startIdx, int target)
{
if (left > right) return -1;
int mid = left + (right - left) / 2;
// 실제 대상 mid index에 회전된 양을 적용한다.
int idxMid = (mid + startIdx) % nums.size();
if (nums[idxMid] == target) return idxMid;
else if (nums[idxMid] > target)
return searchRotatedTargetIdxBS(nums, left, mid - 1, startIdx, target);
else
return searchRotatedTargetIdxBS(nums, mid+1, right, startIdx, target);
}
// 33. Search in Rotated Sorted Array
int search(vector<int>& nums, int target)
{
// find start min index first.
int startIdx = searchMinIdxBS(nums, 0, nums.size() - 1);
if (startIdx < 0) return -1;
return searchRotatedTargetIdxBS(nums, 0, nums.size()-1, startIdx, target);
}
결과
'Leetcode > NeetCode' 카테고리의 다른 글
[LinkedList][Easy] 21. Merge Two Sorted Lists (0) | 2024.07.15 |
---|---|
[LinkedList][Easy] 206. Reverse Linked List. (0) | 2024.07.13 |
[BinarySeach][Medium] 153. Find Minumum in Rotated Sorted Array (0) | 2024.07.12 |
[BinarySearch][Medium] 875. Koko Eating Banans (0) | 2024.07.12 |
[BinarySearch][Medium] 74. Search a 2D Matrix (0) | 2024.07.12 |