[알고리즘] 이진 탐색

이진 탐색이란?

이진 탐색 알고리즘은 정렬된 배열, 리스트에서 원하는 값을 빠르게 찾아낼 수 있는 알고리즘이다.

 

이진 탐색이 얼마나 빠른지는 다른 대표적인 알고리즘인 선형 탐색 알고리즘과 비교해볼 수 있다.

 

선형 탐색의 경우, 앞에서부터 차례대로 탐색하므로 O(n)의 시간복잡도를 갖지만 이진 탐색은 무려 O(log n)의 시간복잡도를 갖는다.

 

하지만 배열이 정렬된 상태에서 이진 탐색이 올바르게 작동함을 유의해야 한다.

 

 

---

 

 

이진 탐색 알고리즘 설명

이진 탐색 알고리즘의 핵심은 탐색 범위를 반으로 좁히는 것에 있다.

 

탐색 범위의 중앙에 있는 값을 보고, 우리가 찾는 값이 어느 범위에 있을지 찾아내는 것이다.

 

따라서 중복 없이 오름차순 정렬된 배열에서 이진 탐색은 아래와 같은 순서로 진행된다.

---

1. 배열 내에서 값 k를 찾을 탐색 범위를 정의
   • 탐색 범위의 첫 위치를 start, 마지막 위치를 end로 정한다.
2. 탐색 범위의 정중앙에 있는 위치(mid)의 원소와 k의 대소 관계를 비교 후 탐색 범위를 반으로 축소
   • mid의 원소 >= k라면 중앙 기준 왼쪽으로 축소
   • mid의 원소 < k라면(나머지 경우) 중앙 기준 오른쪽으로 축소
3. 위 과정을 start와 end가 같아질 때까지 반복

---

위 과정을 거친 뒤 start와 end가 가리키는 값은 배열 내에서 k가 존재할 수 있는 위치를 뜻한다.

 

여기에 있는 원소값이 k와 동일하면 k를 찾은 것이고, 동일하지 않으면 애초부터 배열에 k값이 없다는 의미이다.

 

k값이 아닌 경우 start(또는 end)가 가리키는 원소값은 k보다 큰 원소 중 가장 작은 값이 된다.

 

아래 코드는 위의 실행 순서를 그대로 구현한 것이다.

(리턴값은 배열 내 k가 위치할 수 있는 인덱스이다.)

static int binary_search(int[] arr, int k) {
    int start = 0, end = arr.length;

    while(start < end) {
        int mid = (start + end) / 2;

        if(arr[mid] < k) start = mid + 1;
        else end = mid;
    }
    
    if(arr[start] != k) return -1;

    return start;
}

 

 

---

 

 

이진 탐색에서의 등호 처리

mid와의 비교를 통해 탐색 범위를 반으로 축소시킨다는 아이디어만 동일하다면, 위의 방식이 아닌 다른 방식으로도 이진 탐색을 구현할 수 있다.

 

while문 내에서 arr[mid]와 k가 동일하다면 바로 mid를 리턴해버리는 방식도 가능하고, 위의 코드와 비교했을 때 if문 내 조건에서 등호를 포함하는 방식을 다르게 설정하는 것도 가능하다.

 

하지만 지금부터 if문 내 조건에서 등호를 어디에 포함시키는지에 따른 결과를 생각해보자.

 

위의 binary_search()에 따르면, arr[mid] == k인 경우 end를 좌측 이동시켜 좁혀진 탐색 범위에 mid를 포함시킨다.

 

따라서 최종적으로 start와 end가 가리키는 위치에는 k값이 존재하게 된다.

 

반면 arr[mid] == k에서 start를 우측 이동시킨다면 결과는 어떻게 달라질까?

 

start = mid + 1; 이므로 최종적으로 k값보다 한칸 오른쪽 위치를 가리키게 되어, k값이 있는 인덱스를 리턴하려면 start - 1을 리턴해야 한다.

 

위 내용을 이해했으면 중복된 원소가 있는 배열에서의 이진 탐색도 어렵지 않게 이해할 수 있다.

 

 

---

 

 

중복 허용 배열에서의 이진 탐색

배열 내에서 중복을 허용하는 경우에서도 이진 탐색을 진행할 수 있다.

 

하지만 등호를 어떻게 처리하는지에 따른 결과가 더욱 크게 두드러진다.

 

먼저 arr[mid]가 k값과 동일한 경우 end를 좌측 이동한다고 가정했을 때, 최종적으로 start와 end가 가리키는 위치는 k값을 가지는 최초의(가장 왼쪽의) 인덱스이다.

 

그 이유를 이해하기 위해 극단적인 예시를 생각해보자.

arr의 모든 원소가 k라고 했을 때, mid가 가리키는 값은 무조건 k일테니 범위가 왼쪽으로 좁아진다.
이후에도 mid가 가리키는 값은 무조건 k이므로 왼쪽으로 계속 좁아질 것이고, 최종적으로 end == 0이 된다.

 

다음으로 arr[mid]가 k값과 동일할 때 start를 우측 이동한다고 가정하면, 최종적으로 start와 end가 가리키는 위치는 k값을 초과하는 최초의 인덱스가 될 것이다.

마찬가지로 arr의 모든 원소가 k인 경우, mid가 가리키는 값은 무조건 k일테니 범위가 오른쪽으로 좁아진다.
이를 계속 반복하면 start == n - 1, end == n이 되는데, 이때 mid == n - 1이므로 start == end == n이 된다.

 

위의 두 가지 경우에서 start와 end가 가리키는 인덱스를 각각 하한(lower bound), 상한(upper bound)라고 한다.

참고: 하한과 상한의 정의
먼저 하한의 정의는 실수의 부분집합 S에 대해 S의 모든 원소보다 작거나 같은 원소 중 가장 큰 값이라고 한다.
만약 집합 S를 k가 존재하는 위치(인덱스) 집합이라고 한다면 S의 하한은 k의 인덱스가 될 것이다.
이진 탐색 예시 코드에서 binary_search()가 리턴했던 위치가 곧 S의 하한이라고 볼 수 있다.

상한의 수학적 정의는 S보다 크거나 같은 원소 중 가장 작은 값이라고 한다.
알고리즘에서는 S를 초과한 원소 중에서 가장 작은 값으로 약속한 듯하다.
집합 S를 k가 존재하는 위치(인덱스) 집합이라고 한다면 S의 상한은 k의 인덱스의 1칸 뒤의 위치가 될 것이다.

 

상한과 하한을 이해하면, 배열 내에 특정 원소가 몇 개가 있는지 상한 - 하한을 계산해 알아낼 수 있다.

 

그리고 상한과 하한을 이해하면 인덱스의 위치를 통해 더 많은 문제를 해결할 수 있는데, 개인적으로 아래 문제들을 추천한다.

(탐색에 대한 이해를 넓혀주어 많은 공부가 되었다)

• 랜선 자르기
• 나무 자르기

---

참고한 글들

https://developmentspace.tistory.com/55

 

https://keepgoing0328.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-lowerbound-upperbound