지금 바로 떠나자 먹으러....

문제:

정렬된 정수형 배열과 삽입하려는 정수 값이 인수로 입력되면 해당 값이 삽입 될 배열의 인덱스를 리턴하는 함수를 구현하라.

단, 배열 내에 중복이 존재할 수 없다. 따라서 이미 배열에 값이 존재한다면 해당하는 값의 인덱스를 리턴한다.

예제 1:

Input : [1,3,5,6], 5

Output : 2

예제 2:

Input : [1,3,4,5], 2

Output : 1

예제 3:

Input : [1,3,5,6], 7

Output: 4

풀이:

바이너리 탐색 알고리즘을 활용하여 값을 찾아간다.

바이너리 탐색 알고리즘은 중간 값을 구해서 중간 값이 타겟이 되는 값보다 크다면 왼쪽 편을 탐색하고 작다면 오른 쪽을 탐색하는 알고리즘이다.

배열에서 중간이 되는 인덱스를 구하는 것은 작은 쪽 인덱스와 큰 쪽 인덱스를 합쳐서 2로 나눈 값이다.

예를 들면 크기가 5인 배열은 0부터 4까지의 인덱스를 가지고 있다. 작은 쪽 인덱스 low는 0 큰 쪽 인덱스 high는 4라면 (0+4)/2 = 2, 

즉, 중간 값의 인덱스 mid는 2가 된다.

식은 다음과 같다

mid = (low + high) / 2

그리고 만약 목표가 되는 값을 찾았다면 바로 mid 값을 리턴하주면 되고,

목표가 되는 값이 mid에 들어있는 값보다 크다면 오른 편을 탐색해야 하므로 low에 mid + 1 을 대입한다.

만약 목표가 되는 값이 더 작다면 왼쪽을 탐색해야 하므로 high에 mid - 1 을 대입한다.

low가 high보다 작거나 같다면 위의 방법을 계속 반복해준다.

해당 반복문이 종료되면 우리가 구하려는 값은 low가 된다.

Java code:

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