[알고리즘] 이진 탐색

알고리즘 카테고리의 글을 작성하는 건 정말 오랜만인 것 같다.

아무래도, 최근 코딩 테스트 준비를 하고 있어서 그런가.

볼일도 많고 자료를 알아보니 거의다 예전 자료들 밖에서 없어서 최근에 공부하고 정리한 내용을 전달하고자 오랜만에 작성해보려고 한다.

이진 탐색은 무엇인가

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

그래서 이거 왜 쓰는데?

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

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

그리고 우연히 찾은 페이지가 "소나무"라면 그보다 앞으로 더 이동해서 "사랑"을 찾아야한다.

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

무엇보다도 이런 방식으로 단어를 찾는다면, 처음부터 원하는 단어까지 순차적으로 탐색을 하는 것보다 시간이 매우 단축될 것이다.

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

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

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

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

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

동작원리와 예시 코드

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  # 찾지 못한 경우