이진 탐색

이진 탐색은 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다.

순차 탐색

순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.

보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 원하는 원소를 찾을 수 있다.

 

순차 탐색은 이름처럼 순차적으로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하여 검사하여 구현도 간단하다. for문 한번으로 구현할 수 있어서 최악의 경우 시간 복잡도는 O(N)이다.

 

이진 탐색(반으로 쪼개면서 탐색하기)

이진 탐색은 데이터가 정렬되어 있어야지만 사용 가능하다. 이진 탐색은 범위를 절반씩 좁혀가며 탐색하는 특징이 있다.

이진 탐색은 시작점, 중간점, 끝점 3개의 변수를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

 

맨 처음에 이렇게 시작점, 중간점, 끝점을 정한다.

그러면 찾으려는 4는 8보다 작아서 8이후는 버린다.

 

그리고 또 시작, 중간, 끝점으로 나눠서 4를 찾는다.

4는 중간점보다 크고 끝점보다 작아서 찾을 수 있다.

 

이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

한 단계를 거칠 때마다 원소가 평균적으로 절반으로 줄어든다. 

이진 탐색을 구현하는 방법 2가지가 있다. 하나는 재귀 함수를 이용, 다른 하나는 단순 반복문을 이용한다.

 

-재귀적 방법

def binary_search(array, target, start, end):
      mid = (start + end) // 2
      if start > end:
            return None
      if array[mid] == target:
            return mid
      elif array[mid] < target:
            return binary_search(array, target, mid+1, end)
      else:
            return binary_search(array, target, start, mid-1)
     
# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

이런식으로 재귀 함수를 이용해주면 된다.

 

-반복문 사용

def binary_search(array, target, start, end):
      while start <= end:
            mid = (start+end) // 2
            
            if array[mid] == target:
                  return mid
            elif array[mid] < target:
                  start = mid + 1
            else:
                  end = mid - 1
      return None
     
# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

while문을 사용해서 start가 end보다 작거나 같을 때까지만 수행을 한다.

만약 while문이 끝났는데 값이 반환되지 않으면 target 값이 없어서 None을 반환한다.

 

-코딩 테스트에서의 이진 탐색

참고할 소스코드가 없는 상태에서 이진 탐색을 구현하는 것은 어렵다. 그리고 이진 탐색은 코딩 테스트에서 단골로 나오는 문제라서 가급적 외우는 것이 좋다. 

이진 탐색 문제는 범위가 큰 상황을 가정하는 문제가 많다. 따라서 범위가 2,000만을 넘어가면 이진 탐색으로 접근하는 것이 좋다. 처리해야 할 데이터의 수가 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야한다.