이분탐색이란? 이분탐색(이진탐색) 매우 쉬운 설명

1. 탐색(검색) 알고리즘이란?

• 탐색 알고리즘은 주어진 자료에서 특정 값을 찾는 알고리즘입니다. 예를 들어 배열이나 리스트 형태로 주어진 자료에서 특정 숫자를 찾을 때 사용합니다.
• 대표적인 탐색 알고리즘으로는 선형(순차) 탐색(linear search)과 이분 탐색(binary search)이 있습니다.
• 선형 탐색은 배열의 처음부터 끝까지 순차적으로 검색하면서 찾으려는 값과 같은 값을 찾을 때까지 탐색하는 방식입니다.

알고리즘(Algorithm)이란? 알고리즘 쉬운 설명

 

 

 

2. 이분 탐색이란?

• 이분 탐색 알고리즘은 정렬된 자료에서 특정 값을 찾는 알고리즘 중 하나입니다.
• 이분 탐색은 배열이 정렬되어 있다는 가정 하에, 정렬된 배열의 중간값과 찾으려는 값의 크기를 비교하면서 탐색 범위를 반씩 줄여가며 찾으려는 값을 찾는 방식입니다.
• 이진 탐색 알고리즘이라고도 불리며, 자료를 반으로 나누어 찾고자 하는 값과 비교해 찾고자 하는 값이 작으면 왼쪽 부분을, 크면 오른쪽 부분을 탐색하는 방식입니다.
• 이분 탐색은 탐색 범위를 반씩 줄여나가며 탐색하기 때문에, 최악의 경우에도 O(log n)의 시간 복잡도를 가집니다. 이는 선형 탐색보다 훨씬 빠른 속도를 보장합니다.

 

 

 

3. 이분 탐색 알고리즘 파이썬코드

• 아래는 이분 탐색 알고리즘의 파이썬 코드입니다.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2   # 중간값을 찾습니다.
        
        if arr[mid] == target:   # 찾고자 하는 값과 중간값이 같으면 mid를 반환합니다.
            return mid
        
        elif arr[mid] < target:   # 중간값이 찾고자 하는 값보다 작으면, 오른쪽을 탐색합니다.
            left = mid + 1
        
        else:   # 중간값이 찾고자 하는 값보다 크면, 왼쪽을 탐색합니다.
            right = mid - 1
    
    return -1   # 값이 없을 경우 -1을 반환합니다.

• 위의 코드는 입력으로 주어진 정렬된 배열 arr에서 target을 찾는 이분 탐색 알고리즘 코드입니다.
  • 처음에는 배열의 처음 인덱스를 left, 마지막 인덱스를 right로 설정합니다.
  • 그리고 while 문을 사용해 left가 right보다 작거나 같을 때까지 반복합니다.
  • 중간값 mid를 찾고, arr[mid]가 target과 같은지 비교합니다. 같으면 mid를 반환합니다.
  • arr[mid]가 target보다 작으면, 오른쪽 부분을 탐색하기 위해 left를 mid + 1로 업데이트합니다.
  • arr[mid]가 target보다 크면, 왼쪽 부분을 탐색하기 위해 right를 mid - 1로 업데이트합니다.
  • 만약 값을 찾지 못하면 -1을 반환합니다.
• 예시:
  • arr = [1, 3, 5, 7, 9, 11, 13],  target = 5
  • 초기 상태: left = 0, right = 6, mid = 3, arr[3] = 7
  • 7은 5보다 크므로, 왼쪽을 탐색합니다. left = 0, right = 2, mid = 1, arr[1] = 3
  • 3은 5보다 작으므로, 오른쪽을 탐색합니다. left = 2, right = 2, mid = 2, arr[2] = 5
  • 5와 찾고자 하는 값이 일치하므로, mid를 반환합니다. 결과값: 2

 

 

 

4. 이분 탐색 알고리즘 시간복잡도

• 이분 탐색 알고리즘의 시간 복잡도는 O(log n)입니다. 이는 탐색할 데이터의 크기가 n일 때, 최대 log n번만에 원하는 값을 찾을 수 있다는 의미입니다.
• 예를 들어, 크기가 16인 배열에서 특정 값을 이분 탐색 알고리즘을 사용해 찾을 경우, 최대 4번의 비교 연산만으로 찾을 수 있습니다. 하지만 크기가 32인 배열에서 같은 값을 찾을 경우 최대 5번의 비교 연산이 필요합니다.
• 이는 이분 탐색 알고리즘이 탐색 범위를 반씩 줄여나가는 방식으로 동작하기 때문입니다. 따라서 이분 탐색 알고리즘을 사용하면 대용량의 데이터를 빠르게 탐색할 수 있습니다.