진행자

문강민

이진 탐색이란?

이진 탐색이란 데이터가 오름차순으로 정렬되어 있는 리스트에서 특정한 값을 찾아내는 알고리즘이다.

이진 탐색 알고리즘의 방식은 다음과 같다.

1.리스트의 중간에 있는 값과 우리가 찾고자 하는 값을 비교한다.

2.이때 중간값이 구하고자 하는 값보다 작다면 중간값을 최솟값으로 세팅한다.

반대로 크다면 중간값을 최댓값으로 잡는다

3.이 방식을 리스트에서 구하고자 하는 값을 찾을 때 까지 반복한다.

아래는 위 방식을 영상으로 표현한 것 이다.

이진 탐색 코드

def binary_search(list,find): 

    start = 0
    end = len(list)-1

    while start <= end:
        mid = (start + end)//2 

        if list[mid] < find:
            start = mid + 1
        elif list[mid] > find:
            end = mid - 1
        else:
            return mid

이진 탐색의 시간복잡도