[99클럽] 99클럽 코테 스터디 22일차 TIL - 이분탐색 (Binary Search)

 

오늘의 문제

LeetCode - Search Insert Position (출처 하단 표기)

 

문제

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.

 

제한사항

• 1 <= nums.length <= 10⁴
• -10 ⁴  <= nums[i] <= 10 ⁴
• nums contains distinct values sorted in ascending order.
• -10 ⁴  <= target <= 10 ⁴

입출력 예

nums	target	return
[1, 3, 5, 6]	5	2
[1, 3, 5, 6]	2	1
[1, 3, 5, 6]	7	4

 

풀이

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 정렬된 배열에서 target의 인덱스 찾기
        // 찾지 못한다면 추가되어야 할 인덱스 위치 return
        
        int start = 0;
        int end = nums.length-1;
        
        while(start <= end) {
            int mid = start + (end-start)/2;
            
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) start = mid + 1;
            else end = mid - 1;
        }
        
        return start;   // 찾지 못한 경우
    }
}

 

for문을 사용하여 target과 배열의 인덱스를 비교하여 target이 원소의 값보다 작거나 같으면 해당 인덱스를 반환하고, 그렇지 않으면 배열의 길이를 리턴하는 방식으로 풀 수 있는 문제였다. for문을 사용하는 경우엔 항상 모든 인덱스를 순회하게 되므로 O(n)의 시간이 걸리게 된다. 문제에 O(log n)이 언급되어 있는 것을 보고 이진 탐색으로 풀어야겠다고 생각했다.

이진 탐색은 정렬되어 있는 리스트에서 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. nums의 원소가 정렬되어 있으므로 이진 탐색을 이용하여 풀면 시간 복잡도가 O(log n)이 걸린다는 것을 알 수 있다.

 

먼저 배열의 중간 인덱스를 찾은 후, 배열의 중간값을 기준으로 target을 비교한다. target이 중간값보다 작으면 end 위치를 mid-1로 바꾸고, 다시 start와 end 사이의 중간값을 찾아가면서 target을 찾는다. 반대로 target이 중간값보다 크면 start를 mid+1로 바꾼 다음 다시 start와 end 사이의 중간값을 비교하는 과정을 거친다. 만약 이 과정에서 start가 end보다 커진다면 target 원소를 찾지 못한 것이므로 start가 target을 삽입되는 위치가 된다.

 

 

출처: LeetCode, https://leetcode.com/problems/search-insert-position/