이분탐색 (Binary Search)

이분 탐색(Binary Search)

:정렬된 배열에서 특정한 값을 효율적으로 찾는 탐색 알고리즘

 

정렬된 배열에서 중간 값을 선택하여 비교하고 중간 값 보다 작은 경우 왼쪽 부분 배열 대상으로 탐색, 큰 경우 오른쪽 부분 배열 대상으로 탐색하는 과정을 반복하여 특정 값을 찾도록 동작한다.

 

장점

1. 빠른 탐색 속도: 이분 탐색은 탐색 범위를 반으로 나누면서 탐색을 수행하기 때문에, 평균적으로 O(log n)의 시간 복잡도를 가짐
2. 간결하고 이해하기 쉬운 구현: 이분 탐색은 반복문 또는 재귀 함수를 사용하여 구현할 수 있으며, 구현이 간결하고 직관적

단점

1. 정렬된 배열에서만 가능 : 탐색을 수행하기 전에 배열의 정렬을 확인하고 정렬 후 이분 탐색 사용이 가능
2. 추가 메모리 공간 사용 :  탐색 범위를 축소하는 과정에서 추가 메모리 공간을 사용
3. 원하는 값을 찾을 수 없는 경우 발생 : 배열에서 원하는 값을 찾을 수 없는 경우에 대한 고려 필요

활용

1.  배열에서 특정 값을 찾는 경우
2.  특정 값의 인덱스를 찾는 경우
3.  최대.최소 값을 찾는 경우
4.  특정 조건에 해당하는 값을 찾는 경우

시간복잡도

: O(log n)

 

<이분탐색 Python 코드 예시>

def binary_search(start,end,target,array):
    while start <= end:

        mid = (start+end) //2

        if array[mid] == target:
            return mid
        
        elif array[mid] > target:
            end = mid-1
        elif array[mid] < target:
            start = mid+1