이분탐색 (binary search), 아이디어, 작동 원리, 시간 복잡도/성능, 특징, 자바 구현 코드

이분 탐색 혹은 이진 탐색

 

정렬되어 있는 집합에서 원하는 값을 찾는 효과적인 탐색 방법으로 알려진 이분 탐색에 대해 알아본다.

 

아이디어 

 

큰 틀은 분할 정복 원리를 이용한다. 

-> 배열의 가운데 원소 A[mid]와 탐색키 x를 비교한다.
-> 이 때 3가지 케이스로 나뉜다.

(1)탐색키=가운데원소 → 탐색성공(인덱스mid반환후종료) 

(2)탐색키<가운데원소 → 순환호출 (이진 탐색(원래 크기 1/2의 왼쪽 부분배열))

(3)탐색키>가운데원소 → 순환호출 (이진 탐색(원래 크기 1/2의 오른쪽 부분배열))

 

*mid = ( 시작인덱스 i + 마지막 인덱스 i )/ 2

 

 

- 분할 과정: 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할. 탐색키와 가운데 원소가 같으면 가운데 원소의 배열 인덱스를 반환/종료

 

- 정복 과정: 탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출

 

- 결합: 필요 없음

작동 원리 

 

다음과 같은 데이터를 정렬하는 과정을 통해 실제 작동 원리를 살펴보자 .

 

int arr[] = {10, 15, 20, 25, 30, 35, 40, 45, 50}

 

 

전체 과정 

 

탐색키가 50일 때를 살펴보자. 

 

i) 

10 15 20 25 30 35 40 45 50 

 

이때

left = 0 -> 10

right = 8  -> 50 

mid = 4 -> 30

 

ii) 

10 15 20 25 30 35 40 45 50 

left = 5 -> 35

right = 8  -> 50 

mid = 6 -> 40

 

iii) 

10 15 20 25 30 35 40 45 50 

left = 7 -> 45

right = 8  -> 50 

mid = 7 -> 45

 

iV)

10 15 20 25 30 35 40 45 50 

left = 8 -> 50

right = 8  -> 50 

mid = 8 -> 50

 

 

 

실제 코드 작동을 살펴보자. 

 

 

 

 

 

 

 

 

시간 복잡도 (성능) 

 

배열 크기 n에 대한 이진 탐색의 최대 분할 횟수와 최대 비교횟수는 어떻게 될까? 

 

n개의 데이터에서 대해서 

 

1) n 번 

2) n/2 번

3) n/2^2번 

.

.

.

k+1) n/2^k =1 

 

만큼 분할하므로 k= floor(log2n)

 

최대 비교횟수는 처음 한번을 더해주어 최대 분할횟수 k+1로 볼 수 있다. 

 

따라서 T(n) = 입력 크기 n에 대한 탐색 과정에서의 모든 비교 횟수의 합 

                   = 맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수

 

이 점화식을 풀면 

T(n) = O(logn)이다. 

 

 

 

 

 

특징

 

1. 분할 정복 방식을 이용한다.

 

2. 입력 데이터가 정렬이 되어 있을 때에만 가능하다. 

 

3. 데이터 정렬 상태를 유지하기 위해 평균 n/2개의 데이터 이동 발생 -> 삽입 삭제가 많은 응용에는 적합하지 않을 수 있다. 

 

 

 

 

자바 구현 코드 

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class BinarySearch {

   public static void main(String[] args) {
      test();
   }

   @Test
   public static void test() {
      Assertions.assertEquals(8, binarySearch(new int[] {10, 15, 20, 25, 30, 35, 40, 45, 50}, 0, 8, 50));
   }

   public static int binarySearch(int[] arr, int left, int right, int target) {
      if (left > right) {
         return -1; // 탐색 실패 시 -1을 반환
      }

      int mid = (int)Math.floor((left + right) / 2);

      if (target == arr[mid]) {
         return mid;    // 탐색 성공 시 인덱스 mid를 반환
      } else if (target < arr[mid]) {
         return binarySearch(arr, left, mid - 1, target); // 왼쪽 부분 배열을 탐색
      } else {
         return binarySearch(arr, mid + 1, right, target); // 오른쪽 부분 배열을 탐색
      }
   }

}