leetcode 공부 Day3 (BinarySearch Final)

금일 공부하기전에 내가 풀어왔던 문제를 다시 한번씩 보면서 어떻게 돌아가고 테스트케이스를 보면서 복습을 하는것이 중요하다고 생각된다.

 

풀기전에 느끼지만 Binary Search 알고리즘에서는 mid(중간값) 변수가 중요하다고 생각된다. 그것이 핵심이기 떄문이다.

계속 반으로 나누어서 비교하기 위해서는 제3자의 변수(mid)가 필요하고 이를 활용하여 문제를 접근해야하는 것이 포인트다.

 

35. Search Insert Position

Easy

9931474Add to ListShare

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.

 

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

이 문제는 그동안 풀어왔던 문제와 매우 흡사하다 차이점은 만약 타겟이 없을경우 조치가 다르다는 점이다.

 

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
    int end = nums.length-1;
    int result = -1;
    if(target > nums[end]){
    return end+1;
        }
    while(start <= end){
int mid = start + (end - start)/2;

if(nums[mid] < target){
start = mid+1;
}

        if(nums[mid] > target){
end = mid-1;
}

        if(nums[mid] == target){
    result = mid;
break;
}
    
}
    if(result == -1){
result = start;
}
return result;
    }
}

필자는 그동안 해왔던 것 처럼 start,end , result값을 미리 지정하고 만약 타켓이 배열의 마지막 값보다 클경우 배열위치+1로 미리 지정을 해주고 while문을 작성하였다.

 

작동은 매우 비슷하고 마지막에 그래도 찾을 수 없을 수 없는 값이면 기본-1를 result값을 While문이 빠져나간 start 값으로 넣어서 해결할 수 있었다.

input ex: 1 3 5 6 target=2

TestCase	start	mid	end	result
1	0	1	3	-1
2	0	0	0	-1
3	1	0	0	-1
4	While 을 빠져나오면서	맨 마지막 IF절이 실행	따라서 start 위치를 리턴	1

그동안 데이터베이스뿐만 아니라 알고리즘을 비록 하루에 한 문제씩 이해할 때까지 풀면서 느꼈지만, 계속 풀다 보니 비슷한 유형 문제를 쉽게 접근하여 풀 수 있었고 그만큼 재미가 배가 되는 것을 느꼈다.

 

다음 알고리즘은 Two Pointers 에대해서 알아볼 예정이다.