문제 설명
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
중복 없이 정렬된 배열과 타겟 값이 주어진다. 만약 배열 안에 타겟이 있다면 해당 인덱스를 리턴하시오. 타겟이 없다면, 배열 안에 타겟이 삽입 된 후의 타겟 인덱스를 리턴하시오. 단, 시간 복잡도 O(logn)이 되어야 한다.
출력 예시
접근 방법
첫번째시도
이분 탐색이지만 타겟이 있는 경우와 없는 경우를 한꺼번에 고려할 수 있도록 한다.
소스코드
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int start=0;
int end=nums.size()-1;
bool flag_big = false;
bool flag_small=false;
int cur;
while(start<=end){
cur = (start+end)/2;
if(nums[cur]> target){
end = cur-1;
}
else if(nums[cur]< target){
start = cur+1;
}
else return cur;
}
if(target > nums[cur]) return cur+1;
else return cur;
return cur;
}
};돌아보기
문제는 맞혔지만 while문 이후 바로 start 값을 리턴하면서 시간을 더 단축시킬 수 있었다. (7ms -> 4ms)
while문이 완료 된 후 start = end + 1 이 된다.
nums = [1,3,5,6], target = 7 인 경우 while문 이후의 값은
start = 3 + 1 = 4 이므로, 타겟이 삽입 된 후 인덱스와 같다.
nums = [1,3,5,6], target = 4 인 경우 while문 이후의 값은
end = 2 -1 = 1 이므로, start = 1 + 1 = 2가 되고, 역시 타겟이 삽입 된 후 인덱스와 같다.
타겟보다 작은 값에서 끝나면 start가 증가하고, 큰 값에서 끝나면 end가 감소하는 원리.
