[알고리즘] 이진 탐색(Binary Search)

이진 탐색(Binary Search)

- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하여 원소 하나씩 확인해야 하는 순차 탐색보다 빠르다.

- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. (데이터가 무작위일 때는 사용할 수 없음)

 

이진 탐색(Binary Search) 과정

- 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점을 사용해서 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾아간다.

 

1. 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다. (중간점이 실수일 때는 소시점 이하를 버린다)

2. 찾으려는 데이터와 중간점 데이터를 비교하여

• 중간점의 데이터가 더 크다면 끝점을 중간점의 위치 이전으로 옮긴다.
• 중간점의 데이터가 더 작다면 시작점을 중간점의 위치 앞으로 옮긴다.
• 중간점의 데이터와 같다면 중간점 값을 반환한다.

3. 중간점의 데이터와 같을 때까지 위 과정을 반복한다.

 

 

시간복잡도

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

 

 

구현 코드

1. 재귀 함수를 이용한 방법

def binary_search(array, target, start, end): 
  if start > end:
    return None  

  mid = (start + end) // 2
  
  if array[mid] == target: 
    return mid
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  else
    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
   return None