이분 탐색 정리

이분 탐색

이분 탐색이란?

정렬되어 있는 배열에서 탐색을 할 때, 탐색 범위를 반씩 나누어 탐색하는 방법

장단점

• 장점 : 하나하나 살펴보는 기존 탐색에 비해 훨씬 빠르다.
• 단점 : 정렬이 된 상태에서만 사용할 수 있어 사용하기 까다롭다.

 

이분 탐색 방법

1. 데이터 배열을 정렬해준다.
2. 정렬된 배열에서 왼쪽 끝 인덱스 : left, 오른쪽 끝 인덱스 : right를 이용해 중앙값 : mid를 찾는다.
3. mid와 배열에서 찾고자 하는 값(target)을 비교한다.
4. target이 나올 때까지 아래와 같은 탐색 과정을 반복한다

• mid < target : left를 mid + 1로 이동시켜 오른쪽 구간 탐색(mid+1 ~ right)
• mid > target : right를 mid-1로 이동시켜 왼쪽 구간 탐색 (left ~ mid-1)

5. target이 없으면 none을 반환한다.

이분 탐색은 정렬된 데이터 안에서 반씩 나누어 접근하면서 target이 더 크면 큰 수가 있는 분할 배열로, 작으면 작은 수가 있는 분할 배열로 다시 탐색하는 방법이다.
이는 데이터가 정렬되어 있어 오른쪽은 mid보다 더 큰 수가 있고 왼쪽은 mid보다 더 작은 수가 있음을 보장하기 때문에 가능한 방법이다.

이분 탐색 구현 (파이썬)

이분 탐색은 재귀와 반복을 통해 구현할 수 있다.

재귀를 이용한 구현

def binary_search(arr, target, left, right) :
  if left > right :
    return -1

  mid = (left+right)/2
  if arr[mid] == target:
    return arr[mid]
  elif arr[mid] > target :
    return recursion_binary_search(arr, target, left, mid-1)
  else :
    return recursion_binary_search(arr, target, mid+1, right)

반복을 이용한 구현

def binary_search(arr, target):
  left = 0
  right = len(arr) -1

  while left<=right :
    mid = (left + right) / 2
    if arr[mid] == target :
      return arr[mid]
    elif arr[mid] > target :
      right = mid -1
    else :
      left = mid + 1

  return -1

시간 복잡도

처음 시행에 반이 버려지면 -> N/2

그다음 두 번째 시행에 반이 버려지면 -> (N/2) / 2

세 번째 시행에 또 반이 버려지면 -> ((N/2)/2) / 2

...

K번째 실행에는 아래와 같이 나타낼 수 있다.
N/(2^k)


위와 같이 시행했을 때 남은 자료는 한 개이므로 N/(2^k) = 1

시행 횟수인 k에 대해 정리하면 k = log2(N)이다.



따라서 시간 복잡도는 O(logN)이다.