이분탐색 (Binary Search)

기본 개념

---

배열 내의 특정 값을 찾는 기초적인 알고리즘이다. 특정 값을 찾기 위해 모든 데이터를 순차 탐색을 하는 것이 아니라 탐색 범위를 반씩 줄여나가며 탐색을 진행한다는 특징을 가지고 있다.  여기서 중요한 점은 배열이 정렬되어 있어야 한다는 점이다. 특정 조건을 토대로 범위를 절반씩 줄여나가기 때문에 정렬되지 않은 배열에서 이분 탐색은 사용할 수 없다.

 

이분 탐색을 구현할 때 변수를 보통 세 가지를 사용한다. start, mid, end 세 가지 변수를 통해 현재 탐색 범위의 시작은 start, 탐색 범위의 끝은 end, 그 중간 값은 mid로 사용한다.(물론 변수 명은 개인에 따라 바뀔 수 있다). 이 세 변수를 통해 찾으려는 데이터와 중간 값 위체에 있는 데이터를 반복적으로 비교해서 특정 값을 찾는 것이 이분 탐색이다.

 

 

 

예시

---

정렬되어 있는 배열 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]에서 7이라는 값을 이분 탐색으로 찾아보도록 하자. 탐색하려는 구간의 시작 인덱스는 0이고 끝 인덱스는 9다. 구간 시작을 뜻하는 start 변수에는 0, 구간 끝을 뜻하는 end 변수에는 9, 그 중간값을 뜻하는 mid 변수에는 (0+9)/2 값인 4를 넣도록 하겠다. 그럼 이제 4번 인덱스의 값을 확인해보도록 하자.

 

start: 0, mid: 4, end: 9

우리가 찾으려는 값은 7이지만 4번 인덱스에 들어있는 값은 5다. 우리가 찾으려는 값은 찾지 못했지만 우리는 중요한 정보를 얻을 수 있다. 바로 7은 4번 인덱스 이후에 오는 값이라는 것이다. 이분 탐색이 이루어지는 배열은 정렬된 배열이기 때문에 4번 인덱스보다 작은 인덱스에 있는 값들은 모두 5보다 작은 값이라는 것을 알 수 있기 때문이다. 그렇다면 이번에는 start값을 4번 인덱스에 1 더한 값으로 설정하자. mid는 자연스럽게 (5+9)/2 값인 7이 된다.

 

start: 5, mid: 7, end: 9

7번 인덱스의 값은 8이다. 7과 비교했을 때 8은 크기 때문에 7번 인덱스 이후에 오는 값들은 무조건 7보다 큰 값이 될 것이다. 그렇다면 7번 인덱스와 그 이후 인덱스 값들은 제외하고 탐색을 진행한다. 이번에는 end 변수 값을 바꿔야 한다. 7에서 1 줄인 값인 6을 넣어보자. mid 역시 (5+6)/2 값인 5가 된다.

 

start: 5, mid: 5, end: 6

5번 인덱스의 값은 6, 7보다 작으니 start는 mid에 1을 더한 6이 되고 mid 또한 6이 된다.

 

start: 6, mid: 6, end:6

6번 인덱스 값이 우리가 찾던 7인 것을 확인할 수 있다. 지금까지 단 네 번의 탐색만으로 6번 인덱스의 값을 찾아내는 것을 직접 확인했다. 만일 순차 탐색을 통해 6번 인덱스의 7을 찾고자 했다면 7번의 탐색이 필요했다. 3번 차이라 조금 와닿지 않을 수 있다. 그렇다면 이렇게 생각해보자.

 

우리가 크기가 10인 배열에서 9번 인덱스에 있는 10을 찾는다고 해보자. 순차 탐색이라면 10번을 탐색해야 한다. 이분 탐색은 4번의 탐색이 필요하다. 만일 이 배열의 크기가 두배로 늘어난다고 해보자. 인덱스 19번에 있는 20이라는 숫자는 순차 탐색으로 20번 탐색해야 한다. 기존 탐색 횟수에서 두배가 늘어났다. 하지만 이분 탐색은 기존 탐색 횟수에서 단 1번밖에 늘어나지 않은 5번의 탐색이면 20을 찾을 수 있다. 한 번의 탐색으로 0번부터 9번까지 인덱스는 탐색하지 않아도 된다는 것을 확인할 수 있기 때문이다.

 

위와 같은 탐색방법을 코드로 구현하면 다음과 같다.

board = [(i+1) for i in range(10)]

start = 0
mid = 0
end = 9
while start <= end:
    mid = (start+end)//2

    if board[mid] == 7:
        print(board[mid])
        break
    elif board[mid] > 7:
        end = (mid-1)
    else:
        start = (mid+1)

 

 

 

예시 문제

---

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

 

참고

---

https://velog.io/@kimdukbae/이분-탐색-이진-탐색-Binary-Search

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)