내 테마에 조금 어긋나긴하지만 그래도 바이너리 서치 문제를 한번 풀어봤는데 재밌었다. target 이 주어졌을때 가장 첫번째 위치와 가장 마지막 위치를 return 하면 되는 문제다.
만약에 없으면 -1,-1을 리턴하면 된다. 이 문제에서 가장 먼저 첫번쨰 target 을 바이너리 서치로 찾아봤고 가장 먼저 나온 구간을 탐색하기 위해서 target 을 찾았어도 end 구간을 줄여줬다.
가장 마지막에 나온 구간을 탐색하기 위해서는 left 구간을 늘려줬다.
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> answer(2,-1);
int start = 0, end = nums.size()-1;
while(start <= end){
int mid = start + (end - start) / 2;
if(nums[mid] == target){
answer[0] = mid;
end = mid - 1;
}
else if(nums[mid] < target) start = mid + 1;
else end = mid - 1;
}
start = 0, end = nums.size()-1;
while(start <= end){
int mid = start + (end - start) / 2;
if(nums[mid] == target){
answer[1] = mid;
start = mid + 1;
}
else if(nums[mid] < target) start = mid + 1;
else end = mid - 1;
}
return answer;
}
};