[탐색알고리즘]이분탐색

0. 여러분의 개발 공부에 도움이 되지 않는다.

 

1. 이분탐색 정의 

 - 정렬되어있는 배열 또는 리스트에서 탐색을 하는 방법

 - 검색 범위를 절반씩 줄여 탐색하므로 빠르다.

 

2. 예시 코드 

# 이분탐색 함수
def binary_search(sort_list, key):
    pl = 0 # 리스트의 처음을 pl으로 잡는다.
    pr = len(sort_list)-1 # 리스트의 마지막을 pr로 잡는다.

    while True:
        pc = (pl+pr) // 2 # 중간 수를 pc로 잡는다.(pr//2 로 하지 않은 이유는 아래를 보면 알 수 있다.)
        if sort_list[pc] == key: # sort_list의 인덱스가 pc인 값과 Key가 같다면 바로찾음
            return 1
        elif sort_list[pc] < key: # sort_list의 인덱스가 pc인 값이 key보다 작다면 pc+1을 pl로 만든다.
            pl = pc + 1
        else: # sort_list의 인덱스가 pc인 값이 key보다 크다면 pc11을 pr로 만든다.
            pr = pc - 1
        
        if pl > pr: # pl과 pr이 교차되면 반복문 탈출
            break
    return 0 # 위 조건을 모두 만족 못한다면 없는거임


 # 퀵 정렬 방식으로 N_list를 오름차순으로 정렬한다.
for element in M_list: # 처음 Input으로 받은 M_list의 element를 뽑아내 정렬된 sort_N 리스트를 이분법으로 조회한다.
    print(binary_search(N_list, element))# 이분법 함수로 보냄