국어 사전과 이진 탐색의 공통점

이진 탐색은 무엇인가

이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.

그래서 이거 왜 쓰는데?

국어 사전을 살펴본다고 가정하자. (지금은 잘 쓰지 않지만)

"사랑"이라는 단어를 찾아본다고 할 때, 우선 "ㅅ"에 해당하는 파트로 이동해야한다.

그리고 우연히 찾은 페이지가 "소나무"(사전순으로 봤을 때에 사랑보다 뒤에 위치한다)라면 그보다 앞으로 더 이동해서 "사랑"을 찾아야한다.

이런식으로 내가 원하는 단어와 현재 단어의 순서를 비교하며 찾아간다는 점이 유사하다고 할 수 있다.

뿐만 아니라, 해당 방식은 처음부터 원하는 단어까지 순차적으로 탐색을 하는 방식보다 시간이 매우 단축될 것이다.

이진 탐색을 사용할 수 있는 조건

앞서 예시를 둔 국어 사전은 기본적으로 사전순으로 정렬이 되어있다

따라서, 현재 단어의 위치를 파악하여 앞으로 갈지 뒤로 갈지를 판단할 수 있다.

이진 탐색도 마찬가지이다.

현재 데이터의 위치를 파악하여 앞으로 갈지 뒤로 갈지를 판단해야하기 때문에 정렬된 리스트에서만 사용할 수 있다.

동작원리와 예시 코드

1. 탐색할 배열을 정렬한다.

2. 배열의 중간 인덱스 값을 기준으로 탐색을 시작한다.

3. 중간 값과 찾고자 하는 값을 비교한다.

   3-1. 중간 값이 찾고자 하는 값보다 작으면 왼쪽 부분 배열을 탐색한다.

   3-2. 중간 값이 찾고자 하는 값보다 크면 오른쪽 부분 배열을 탐색한다.

4. 찾고자 하는 값이 중간 값과 일치하면 해당 위치를 반환하고, 아니면 반복하여 탐색을 진행한다.

5. 탐색할 부분 배열의 크기가 0이 될 때까지 위의 과정을 반복한다.

def binary_search(arr, target):
    left = 0
    right = len(arr)-1
    
    while left <= right:
        mid = (left+right)//2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid+1
        else:
            right = mid-1
    
    return -1  # 찾지 못한 경우

블로그 : https://justgotothedesk.tistory.com/152

예시 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/64062