이진 탐색 알고리즘

이진 탐색 알고리즘

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

 

이진 탐색 동장 예시

1. 이미 정렬된 10개의 데이터 중에서 값을 찾는 방법
2. 시작점, 끝점과 중간점을 설정한다. - 중간 값이 2개일 경우 소수점 이하 제거
3. 중간점을 기준으로 찾는 데이터가 우측에 있는지 좌측에 있는지 구분
4. 만약 좌측에 있다면 시작점은 그대로 내버려두고 현재의 중간점을 끝점으로 수정
5. 수정한 시작점과 끝점을 기준으로 중간점을 다시 설정
6. 이후 중간점 위치의 값이 찾고자하는 데이터가 같아질 때까지 반복

 

 

시간복잡도

단계마다 탐색범위를 2로 나누는것과 동일하므로 연산 횟수는 log(2) N에 비례한다.

 

 

소스코드

# 이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

 

 

파이썬 이진 탐색 라이브러리

bisect_left(a, x) # 정렬된 순서를 유지하면서 배열 a에 x를 삽일할 경우 가장 왼쪽 인덱스를 반환
bisect_right(a, x) # 정렬된 순서를 유지하면서 배열 a에 x를 삽일할 경우 가장 오른쪽 인덱스를 반환

 

값이 특정 범위에 속하는 데이터 개수 구하기

 

 

파라메트릭 서치

최적화 문제를 결정 문제로 바꾸어 해결하는 기법

• 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.