이진 탐색 알고리즘에 대해 알아보자

이진 탐색 알고리즘에 대해 알아보자

이진 탐색(binary search)

● 정의

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

 

● 특징

1. 배열의 내부 데이터가 정렬되어 있어야만 사용 가능

2. 변수 3개(start, end, mid)를 사용하여 탐색. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복 비교하며 원하는 데이터를 찾는다.

3. 시간복잡도가 O(log N) 이다.

 

● 구현 코드 (Python)

# 이분탐색

array = [4,3,5,1,2,6] # 정렬되지 않은 배열
array = sorted(array) # sorted 로 정렬하기 
print("array:",array)

def binary_search(array, target, start, end):
    if start > end: # 탐색이 끝났음에도 값을 찾지 못한 경우
        return None
    mid = (start + end) // 2
    print(array[mid])
    # 원하는 값 찾은 경우 값을 반환
    if array[mid] == target:
        return array[mid]
    # 원하는 값이 중간 값보다 작은 경우 왼쪽부분 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 원하는 값이 중간 값보다 큰 경우 오른쪽부분 확인
    else:
        return binary_search(array, target, mid + 1, end)

result = binary_search(array, 2, 0, len(array) -1)

if result is None:
    print("원소가 존재하지 않습니다.")
else:
    print("원소는 "+str(result)+"입니다.")

● 코드 과정 설명