24-06-20 이진 탐색 알고리즘

오늘은 AWS 강의를 주로 들으면서 시간을 보냈다. AWS 서비스들에 대해 소개되어있는 강좌였는데 듣고나니 앞으로 어떤 걸 더 공부해야할지 어느정도 깨달을 수 있었다. 앞으로 배워야할게 많이 남은 것 같으니 더 열심히 공부해봐야겠다.

 

여기에는 간단하게 오늘 간단하게 공부해본 이진 탐색 알고리즘에 대해 정리해본다.

 

1. 이진 탐색 알고리즘

1-1. 이진 탐색 알고리즘이란?

이진 탐색 알고리즘은 정렬된 데이터에서 원하는 값을 찾는 검색 알고리즘이다. 값을 찾아내는 시간 복잡도가 O( $\log n$)인 알고리즘이다.

 

이진 탐색 알고리즘의 원리는 아주 간단하다.

 

먼저 위 사진과 같이 정렬된 데이터가 있어야한다. 우리는 17개의 숫자중에서 '7'을 찾고 싶은 상황이다.

 

먼저 전체 데이터의 절반(0~16)에 해당하는 곳(8번째)의 값과 원하는 값을 비교한다. '14'보다 '7'이 작기 때문에 이제 앞 부분 (0~7)에서 원하는 값이 있는지 찾아보면 된다.

 

0~7은 짝수 개의 숫자이기 때문에 정확히 중간이 없어서 (0 + 7)을 2로 나눈 나머지인 3번째 값과 원하는 값을 비교한다. 이번에는 '6'이 '7'보다 작기 때문에 다음 번에는 (4~7)에서 원하는 값이 있는지 찾아보면 된다.

 

이번에도 4~7은 짝수 개의 숫자이기 때문에 정확히 중간이 없어서 (4 + 7)을 2로 나눈 나머지인 5번째 값과 원하는 값을 비교한다. '8'이 '7'보다 크기 때문에 이제 남은 숫자는 4번째 숫자만이 남는다. 바로 이 4번째 숫자가 우리가 원하는 값인 '7'이다.

 

위와 같은 예시는 범위가 크지 않아 이 이진 탐색 알고리즘이 얼마나 효과적인지 잘 체감되지 않지만 수백, 수천만개 값이 있어도 이 이진 탐색 알고리즘을 이용하면 30번도 채 걸리지 않아 값을 찾을 수 있다.

 

1-2. 이진 탐색 알고리즘을 사용할 때 주의해야할 점

이진 탐색을 이용할 때 투 포인터를 이용하여 값을 조정하는 방식으로 코드를 작성하게 된다.

 

왼쪽 포인터를 left 오른쪽 포인터를 right라고 한다면 중간점은 (left + right)/2가 된다. 만약 찾는 값이 중간점보다 작다면 오른쪽 포인터가 (중간점 - 1)이 되고, 중간점보다 크다면 왼쪽 포인터가 (중간점 + 1)이 된다.

 

그런데 위와 같이 이진 탐색을 사용하면 문제가 발생할 가능성이 있다. left와 right가 아주 큰 수여서 left와 right의 합이 자료형의 최대값을 넘어가면 오버플로우가 발생하게 된다는 것이다. 두 수의 합을 구한 뒤 2로 나눈 나머지를 구하면 이상한 값이 나오게 될 것이다.

 

이것은 아주 쉽게 해결할 수 있는데 중간점을 구할 때 (left + right)/2로 구하는 것이 아니라 left + (right-left)/2 로 구하는 것이다. 위와같이 중간점을 구하게 되면 right가 시작부터 표현범위를 넘어가는 값이 아니고서야 오버플로우가 발생할 수가 없다.

 

1-3.  코드로 구현해 본 이진 탐색

아주 간단하고 기본적인 이진 탐색 문제인 leetcode에 있는 '704. Binary Search' 문제를 풀어보았다.

 

[문제]

오름차순으로 정렬된 정수로된 nums 배열과 정수인 target이 주어졌을 때, nums에서 target을 검색하는 함수를 작성하세요. target이 존재하면 그 인덱스를 반환하세요. 아니면 -1을 반환하세요.

 

시간 복잡도가 반드시 O( $\log n$)인 알고리즘을 작성해야 합니다.

 

- 예시 1

입력: nums = [-1, 0, 3, 5, 9, 12], target = 9

출력: 4

설명: 9가 nums에 있고 인덱스는 4이다

 

- 예시 2

입력: nums = [-1, 0, 3, 5, 9, 12], target = 2

출력: -1

설명: 2는 nums에 없기 때문에 -1을 반환한다

 

- 제한 사항:

• $ 1 {\;}{\leq}{\;} nums.length {\;}{\leq}{\;} 10^{4} $
• $ -10^4 {\;}{\leq}{\;} nums[i], target {\;}{\leq}{\;} 10^{4} $
• nums는 모두 서로 다른 정수로 이루어져 있다
• nums는 오름차순으로 정렬되어 있다

 

[풀이]

 

아주 간단한 이진 탐색 문제이기 때문에 설명을 크게 덧붙이지는 않고 작성한 코드를 올려본다.

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        // nums에 target이 없으면 -1을 반환해야하므로 -1로 초기화
        var answer = -1
        var left = 0
        var right = nums.size - 1

        while (left <= right) {
            // 중간 값
            val middle = left + (right - left) / 2

            when {
                nums[middle] < target -> left = middle + 1
                nums[middle] > target -> right = middle - 1
                else -> {answer = middle; break}
            }
        }

        return answer
    }
}

위와 같이 코드를 작성하면 답안으로 잘 통과된다.

 

여기까지 이진 탐색에 대해 알아보고 가장 기본적인 문제까지 풀어보았다.

 

알고리즘도 하나하나 보다보면 꽤 재미있는 것 같다. 앞으로도 꾸준히 문제도 풀고 이론도 공부해보는 시간을 가져봐야겠다.

 

 

2. 오늘 배운 것

- AWS의 서비스들에 대해 간략하게 훑어볼 수 있었다. 필요한 서비스들을 잘 사용할 수 있도록 앞으로 공부해보아야겠다.

- 이진 탐색 알고리즘에 대해 공부해보았다.