[이진탐색] 범위를 반씩 좁혀가는 탐색

 

순차 탐색

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

보통 정렬되어있지 않은 리스트에서 데이터를 찾아야 할때 사용

시간복잡도는 O(N)이다.

 

 

이진 탐색

데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

시작점,끝점,중간점으로 범위를 나누어 탐색한다.

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터를 찾는다

 

STEP 1 시작점과 끝점을 확인한 다음 둘 사이 중간점을 시작점과 끝점을 더한 값을 2로 나눈 값으로 한다. 

다음으로 중간점[4]의 데이터와 8과 찾으려는 데이터 4를 비교한다. 중간점의 데이터 8이 더 크므로 중간저 이후의 값은 확인 할 필요가 없다. 그래서 끝점을 [4]의 이전인 [3]으로 변경

 

STEP 2 1과 같은 방법을 수행한다.

 

 

 

STEP 3 이제 중간점의 인덱스에 위치한 값이 찾는 데이터이므로 탐색을 종료한다.

 

 

 

파이썬 재귀함수로 구현한 이진탐색

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

 

파이썬 반복문으로 구현한 이진탐색

# 이진 탐색 소스코드 구현 (반복문)
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)

 

 

 

코딩테스트에서의 이진탐색

이진 탐색이 단순하다고 느낄 수 있지만 정작 구현을 하려고 하면 어렵고 복잡하다.

또한 코딩 테스트에 자주 나오니  자연스럽게 반복 숙달하며 직접 코드를 치며 외우자.

또한 탐색의 양이 많을 떄는 순차탐색이 아닌 이진탐색을 해야 한다.

약 2000만개 이상이라면 이진탐색을 사용하자