이진검색

이전검색이란?

이진 검색(Binary Search)은 정렬된 데이터 집합에서 효율적으로 특정 값을 찾는 검색 알고리즘입니다. 이진 검색은 "분할 정복(Divide and Conquer)" 전략을 사용하여, 검색 범위를 반으로 줄여가며 찾고자 하는 값을 빠르게 찾습니다.

 

작동 원리

 

이진 검색의 기본 아이디어는 다음과 같습니다:

1. 중앙 요소 확인: 정렬된 배열에서 중앙에 위치한 요소를 확인합니다.

2. 탐색 범위 축소: 찾고자 하는 값이 중앙 요소보다 작으면, 중앙 요소의 왼쪽 부분에서 검색을 계속합니다. 찾고자 하는 값이 중앙 요소보다 크면, 중앙 요소의 오른쪽 부분 에서 검색을 계속합니다.

3. 반복: 새로운 검색 범위 내에서 다시 중앙 요소를 찾고, 2번 과정을 반복합니다.

4. 종료 조건: 찾고자 하는 값이 중앙 요소와 일치하면 검색을 종료하고 그 위치를 반환합니다. 검색 범위가 더 이상 없을 때까지 값을 찾지 못하면, 해당 값이 배열에 존재 하지 않는다고 판단하고 검색을 종료합니다.

 

이진 검색의 장점

효율성: 이진 검색은 O(log n) 의 시간 복잡도를 가집니다. 여기서 n 은 배열의 크 기를 의미합니다. 이는 큰 데이터 집합에서도 빠른 검색 속도를 보장합니다.

정렬된 데이터에 최적화: 이진 검색은 데이터가 사전에 정렬되어 있을 때 사용할 수 있습니다. 정렬된 배열에서 매우 빠르게 작동합니다.

이진 검색의 단점

데이터 정렬 필요: 이진 검색을 사용하기 전에 데이터가 정렬되어 있어야 합니다. 따 라서 정렬되지 않은 데이터 집합에서는 직접 사용할 수 없습니다.

동적 배열에서 비효율적: 배열에 자주 삽입이나 삭제가 발생하는 경우, 배열을 정렬 된 상태로 유지하는 데 추가 비용이 발생할 수 있습니다.

 

예제) 이진 검색: 

import java.util.Scanner;
class BinarySearchExample {
      // 요솟수가 size인 배열 arr에서 key와 같은 요소를 이진 검색
      static int binarySearch(int[] arr, int size, int key) {
            int left = 0; // 검색 범위의 시작 인덱스
            int right = size - 1; // 검색 범위의 끝 인덱스
            while (left <= right) {
                  int mid = (left + right) / 2; // 중앙 요소의 인덱스
                  if (arr[mid] == key)
                        return mid; // 검색 성공
                  else if (arr[mid] < key)
                        left = mid + 1; // 검색 범위를 오른쪽 절반으로 좁힘
                  else
                        right = mid - 1; // 검색 범위를 왼쪽 절반으로 좁힘
            }
      return -1; // 검색 실패
}

 

이진 검색의 시간 복잡도

이진 검색(Binary Search)의 시간 복잡도는 O(log n) 입니다. 여기서 n 은 검색 대상이 되는 데이터 집합의 요소 수를 의미합니다. 이진 검색이 O(log n) 시간 복잡도를 가지는 이유를 이해하기 위해서는 이진 검색의 작동 방식과 "로그(logarithm)"의 개념을 알아야 합니다

 

이진 검색 작동 방식

이진 검색은 정렬된 배열에서 중간 값과 찾고자 하는 키 값을 비교하여 검색 범위를 반으로 줄여나가며 키 값을 찾습니다. 첫 번째 비교를 통해 검색 범위를 절반으로 줄이고, 그 다음 비교에서 다시 절반으로 줄이며, 이 과정을 찾고자 하는 값이 발견되거나 더 이상 검색 범위가 없을 때까지 반복합니다.

 

로그(log) 개념

로그는 지수 함수의 역함수로, O(log n) 의 log 는 밑이 2인 로그를 의미합니다. 밑이 2 인 로그 함수 log2(n) 은 2의 몇 제곱이 n 이 되는지를 나타내는 값입니다. 이진 검색에서는 각 단계마다 검색 범위를 반으로 줄이므로, n 개의 요소를 가진 데이터 집합을 검색할 때 최대 log2(n) 번의 비교를 수행하게 됩니다.

 

시간 복잡도 분석

• 최악의 경우 시간 복잡도: 이진 검색에서 최악의 경우는 찾고자 하는 키 값이 배열에 없거나 검색 범위의 마지막 단계에서 발견되는 경우입니다. 이 경우, 최대 log2(n)번의 비교가 필요하므로 시간 복잡도는 O(log n) 입니다.
• 최선의 경우 시간 복잡도: 최선의 경우는 첫 번째 비교에서 바로 찾고자 하는 키 값 이 중간 값과 일치하는 경우입니다. 이 경우 시간 복잡도는 O(1) 입니다.
• 평균 시간 복잡도: 대부분의 경우, 이진 검색의 평균 시간 복잡도도 O(log n) 으로 볼 수 있습니다. 데이터 집합의 크기가 커질수록 이진 검색의 효율성은 더욱 두드러 집니다.

이진 검색의 O(log n) 시간 복잡도는 큰 데이터 집합에서도 빠른 검색 성능을 보장합니 다. 따라서 데이터가 사전에 정렬되어 있을 때 이진 검색을 사용하는 것은 매우 효율적인 선택입니다.