이코테 2021 - 이진 탐색

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

 

 

 

이진탐색

 

>> 정렬된 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 하는 알고리즘

>> 시작점과 끝점, 중간점을 명시해야 함

 

 

EX) 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기

기본 정렬

> 중간점의 값이 두개가 될 경우, 소수점 이하를 제거(4.5 → 4)하여 중간점을 설정한다.

> 이때, 중간점의 값(8)과 찾고자 하는 값(4)를 비교하여 중간점의 왼쪽 혹은 오른쪽의 값들만 탐색한다.

>> 효율 증가

 

 

> 왼쪽의 값들을 기준으로 시작/끝 점을 재설정한다. 그러면 중간점도 재설정 되므로 중간점은 2 (1.5 → 1) 의 값을 가진다.

> 이때 중간점값(2)보다 찾고자 하는 값(4)이 더 크므로 시작점을 오른쪽으로 옮긴다.

 

> 찾고자하는 값(4)이 중간점과 동일하므로 탐색과정을 멈춘다.

 

 

단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는에 비례한다.
예를 들어, 초기 데이터 개수가 32일 때, 첫번째 단계에서 16개의 데이터로 절반이 줄고,
두번째는 8개, 3단계는 4개의 데이로 탐색 데이터 갯수가 줄어든다

 

 

이걸 파이썬 코드로 구현해보자.

data= [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

first_idx= 0
last_idx= len(data)-1
mid_idx= (first_idx + last_idx)//2
count= 0

point_num= int(input('찾고자 하는 숫자는? '))

def func():
    global first_idx, last_idx, mid_idx, count
    count += 1
    print('first', first_idx, 'mid',mid_idx, 'last',last_idx)
    
    if point_num == data[mid_idx]:
        return 
    elif point_num < data[mid_idx]:
        last_idx = mid_idx - 1
    else:
        first_idx = mid_idx + 1

    mid_idx= (first_idx + last_idx)//2
    
    func()
    
func()
print('인덱스',mid_idx)
print(count,'step 만에 성공')