이진탐색

탐색

컴퓨터 과학에서 탐색이란 여러 개의 원소로 구성된 데이터가 주어졌을 때, 그중에서 원하는 값을 갖는 원소를 찾는 것을 말한다.
데이터의 형태는 리스트, 트리, 그래프 등 다양한 형태가 가능하다.

이진 탐색

이진 탐색, 또는 이분 탐색이란 정렬된 형태로 주어진 원소에 대해 탐색 대상의 크기를 절반씩 줄여 가면서 탐색 키를 가진 원소를 찾는 방식이다.
정렬된 배열에서 탐색 키를 찾는 위해서는 다음의 과정을 거친다:

• 정렬된 배열의 가운데 원소 mid와 탐색 키 key를 비교
• 두 값이 같다면 탐색 종료
• 두 값이 같지 않다면 배열을 mid를 기준으로 나누어 두 개의 배열로 분할
• key > mid일 경우에는 위쪽 부분배열에 이진 탐색 진행
• key < mid인 경우에는 아래쪽 부분배열에 이진 탐색 진행
• key == mid일 때 까지 반복

이진 탐색의 대전제는 원소들의 정렬이기 때문에, 원소들의 정렬 여부를 우선 확인해야 하며,
정렬되어 있지 않은 경우에는 정렬하는 초기화 연산이 필요하다.

알고리즘

이진 탐색은 다음과 같이 표현할 수 있다:

def binarySearch(a : Sequence, key : Any, left : Any, right : Any) -> int:
  #배열 a에서 key와 일치하는 원소를 이진 탐색
  left = 0                            # 검색 범위 맨 앞 원소의 인덱스
  right = len(a) - 1                  # 검색 범위 맨 끝 원소의 인덱스

  if (left > right) return -1
  
  mid = (left + right) // 2           # 중앙 원소의 인덱스
  if a[mid] == key:         
    return mid                        # 탐색 성공, 인덱스 반환
  elif a[mid] < key:      
    ans = binarySearch(a, key, left, mid-1)  # 탐색 범위를 뒤쪽 절반으로 축소
  else:
    ans = binarySearch(a, key, mid+1, right) # 탐색 범위를 앞쪽 절반으로 축소       
  return ans

입력:

• a : 전체 입력 배열. 오름차순으록 정렬되어 있다고 가정
• key : 탐색 키
• left, right : 탐색 대상 구간. a[left..right]에 서 key를 찾아야 함 출력:
• key가 a[right..left]내에 존재하면 해당 인덱스, 존재하지 않을 시 -1 반환

성능 및 특징

시간 복잡도

이진 탐색 알고리즘은 한 번의 순환 호출로 구성되며, 그 때마다 입력 배열의 크기가 절반으로 들어든다.
따라서, 입력 크기 n에 대한 이진 탐색의 수행시간 T(n)은 다음과 같은 점화식으로 표현된다.

T(n) = T(n/2) + O(1)(n>1), T(1) = O(1)

그렇기에, 이진 탐색의 시간 복잡도는 O(n)이다.

삽입과 삭제 연산

이진 탐색을 통한 삽입 연산은 새 원소를 삽입할 위치를 이진 탐색으로 하기 때문에 O(log n)의 시간이 필요하며,
해당 인덱스부터 모든 원소를 한 칸씩 오른쪽으로 이동시켜야 하기 떄문에 O(n)의 시간이 필요하다. O(n) + O(log n) 이기 때문에 이진 탐색의 삽입 연산의 시간 복잡도는 O(n)이다.

삭제 연산 또한 비슷하게 이진 탐색을 통해 삭제할 원소를 찾고 삭제 후에 해당 인덱스부터의 모든 원소를
왼쪽으로 한 칸씩 이동시켜야 하기 때문에 O(n)의 시간 복잡도를 갖는다.

특징

입력이 정렬된 리스트에 대해서만 적용 가능하기 떄문에 입력 데이터의 정렬 여부를 알 수 없다면 초기화 연산을 해주어야 한다.
정렬 함수는 O(n log n)의 시간이 필요하기 때문에 데이터가 적은 경우에 적합하다.