[알고리즘 개념]이진 탐색 알고리즘(Binary Search)

이진탐색은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.

 

이진탐색 알고리즘 구현 로직은 다음과 같습니다.

배열의 중간 요소를 검사하고 목표값이 중간 값과 비교하여 검색 범위를 절반으로 줄여가며 작동합니다.

시간복잡도:O(log n)

 

이진탐색 알고리즘은 반복문을 통한 이진 탐색과 재귀 함수를 사용한 이진 탐색이 있습니다.

 

 

https://hcr3066.tistory.com/23 이미지 출처

반복문을 통한 이진탐색

def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# 예제 사용법
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_iterative(arr, target)

if result != -1:
    print(f"값 {target}은(는) 인덱스 {result}에 있습니다.")
else:
    print(f"값 {target}을(를) 배열에서 찾을 수 없습니다.")

 

재귀함수를 이용한 이진탐색

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 예제 사용법
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

if result != -1:
    print(f"값 {target}은(는) 인덱스 {result}에 있습니다.")
else:
    print(f"값 {target}을(를) 배열에서 찾을 수 없습니다.")

 

 

 

이진탐색 로직

 

입력

1. 배열을 정렬합니다.(arr.sort())

2. target(찾는 값을 입력)을 받습니다.

 

이진탐색 함수

left 값 = 0

right 값= len(arr)-1

반복문 : left<=right 일때 까지 반복

중간값 구하기->mid(중간값)==(left+right)//2

 

케이스 나누기

중간값=target값 : mid 값 반환

 

arr[mid]<target: 중간 값이 타겟 값보다 작다면

left=mid+1

 

arr[mid]>target:중간 값이 타겟 값보다 크다면

right=mid-1