이진 탐색(binary search)

먼저 이 글은 나동빈님의 '이것이 취업을 위한 코딩테스트이다' 이진탐색 파트를공부하고 정리한 것임을 밝힙니다.

---

순차탐색(Sequential Search)

리스트 안에서 특정 원하는 데이터를 찾으려고 할때 

가장 먼저 떠올릴 수 있는 아이디어는

처음부터 하나하나 확인하면서 일치하는 데이터의 인덱스를 뽑아내는 것이다.

 

이를 순차탐색(Sequential Search) 이라고 한다.

반복문과 조건문을 적절히 이용하면 큰 어려움 없이 만들어볼 수 있다.

 

이때의 시간복잡도는 당연히 O(N)이다

이제 더 빨리 찾아낼 수 있는 이진탐색에 대해서 알아보자.

---

이진 탐색(Binary Search)

먼저 이진탐색은 데이터가 정렬이 되어있는 상태에서 사용할 수 있는 알고리즘이다.

 

이진탐색의 아이디어는

위치를 나타내는 변수 3개를 이용한다.

(1. 시작점 2. 끝점 3. 중간점)

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

 

이진탐색의 시간복잡도는 O(logN)이다.

확인해야하는 원소의 개수가 절반씩 줄어들기 때문이다.

 

<구현 방법>

1. 재귀함수 

2. 반복문 

 

1. 재귀함수를 이용해서 이진 탐색 구현하기

 

# 이진탐색 소스코드 구현(재귀 함수)
def binary_search(array,target,start, end):
    if start >= end: # edge case
        print('타겟값이 존재하지 않습니다')
        return None
    mid = (start + end) // 2
    
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target: # base case
        return mid

    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] < target:
        return bianry_search(array,target,start,mid-1)
    
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else array[mid] > target:
        return binary_search(array,target,mid+1,end)

 

2. 반복문을 이용해서 이진 탐색 구현하기

 

# 이진 탐색 소스코드 구현(반복문)
def binary_search(array,target,start,end):
    while start < end:
        mid = (start + end) // 2

        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    print('찾으려는 타겟값이 없습니다')
    return None

 

존 벤틀리라는 사람이  제대로 이진탐색 코드를 작성하는 프로그래머는 10% 내외라고 할 정도로 구현이 까다로운 코드라고 한다.

코딩테스트에 잘 나오는 알고리즘이라고 하니 익숙해지도록 하자.