[Python][이코테] 이진 탐색

이진 탐색

Binary Search

 

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

 

이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.

 

이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 방법이다.

 

---

이진 탐색은 변수 3개를 사용한다. 시작점, 끝점 그리고 중간점

 

예를들어 0 2 4 6 8 10 12 14 16 18 의 배열에서 4를 찾는다고 가정하자

 

0

2

4

6

8

10

12

14

16

18

우선 시작점은 [0], 끝점은 [9] 중간점은 9/2 = 4.5 에서 소수점은 버려서 [4]로 지정한다.

 

[0] = 0, [9] = 18, [4] = 8

 

[4]의 데이터와 찾으려는 값 4를 비교한다. [4]의 값이 더 크므로 중간점 이후의 값은 확인할 필요가 없기에 탐색 범위를 좁힌다.

 

그럼 [4]의 이전인 [3]을  끝점으로 지정하고 다시 중간점을 3/2 = 1.5로 [1]을 중간점으로 지정한다.

 

[0] = 0, [1] = 2, [3] = 6 으로 중간점 [1]의 값은 4보다 작으므로 시작점을 [0][1]을 넘어서 [2]로 변경한다.

 

 

시작점 [2], 끝점[3] 으로 중간점은 5/2 = 2.5 로 [2]에 중간점을 잡는다. 중간점 [2]의 값은 찾고자 하는 값 4와 동일하므로 탐색을 종료한다.

---

위의 방식을 사용하여 데이터의 개수는 총 10개이지만 3번의 비교만하며 값을 찾아낼 수 있었다.

 

이진 탐색은 원소의 개수가 절반씩 줄어들기 때문에 시간복잡도는 O(logN)이다.

 

---

이진 탐색을 구현하는 방법은 단순한 반복문 방식과 재귀 방식 두가지가 있다.

 

1. 재귀 방식

# 7-1 이진 탐색 재귀함수
# 이진 탐색 소스코드 구현(재귀함수)
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)

 

 

 

2. 반복문 방식

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

# 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)