이진탐색(Binary Search)

순차 탐색이란?

 

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

 

- 가장 앞에 있는 원소부터 하나씩 탐색

- 최악의 경우 시간 복잡도는 O(N)

def sequential_search(n, target, array):
  for i in range(n):
    if array[i] == target:
      return i+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) # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인



# 반복문

def binary_search(array, target, start, end):
  while start<= end:	# start가 end보다 작거나 같은 동안 반복
    mid = (start+end)//1	# 중간 인덱스
    if array[mid] == target:	# 중간 인덱스가 타겟이랑 같으면 중간 인덱스 리턴
      return mid 
    elif array[mid] > target:	# 중간 인덱스의 값이 타겟 보다 크면 end 변수는 중간 인덱스에서 -1
      end = mid-1
    else:	# 중간 인덱스의 값이 타겟 보다 작으면 start 변수는 중간 인덱스에서 +1
      start = mid+1
  return -1

 

파이썬은 이진 탐색을 수행하는 bisect 이라는 모듈을 제공한다

import bisect

def binary_search(array, target):
    # bisect_left() 함수를 사용하여 배열에서 target의 삽입 위치를 찾는다
    # bisect_left() 함수는 이미 정렬된 배열에서 target이 들어갈 적절한 위치(왼쪽 끝)를 반환
    index = bisect.bisect_left(array, target)
    
    # 만약 index가 배열의 길이를 초과하지 않고, 해당 위치에 있는 값이 target과 같다면
    if index < len(array) and array[index] == target:
        # 해당 위치(index)를 반환
        return index
    else:
        # 그렇지 않으면, target이 배열에 없으므로 -1을 반환
        return -1

위의 코드에서는 bisect_left 함수를 이용

 

bisect_right 함수도 존재하는데 이 둘의 차이는

 

- bisect_left: 배열에서 삽입할 가장 왼쪽의 위치를 찾는다

- bisect_right: 배열에서 삽입할 가장 오른쪽의 위치를 찾는다.

 

import bisect

arr = [1, 3, 5, 5, 7, 9]

# bisect_left() 함수 예제
index_left = bisect.bisect_left(arr, 5)
print("bisect_left:", index_left)  # 출력: 2

# bisect_right() 함수 예제
index_right = bisect.bisect_right(arr, 5)
print("bisect_right:", index_right)  # 출력: 4

bisect_left는 왼쪽의 위치를 찾기 때문에 2번 째 인덱스를 반환한다

하지만

bisect_right는 오른쪽의 위치를 찾기 때문에 4번 째 인덱스를 반환한다

 

결국

bisect_left = [1, 3, index, 5, 5, 7, 9] index는 2!

bisect_right = [1, 3, 5, 5, index, 7, 9] index는 4!

 

순차 탐색 vs 이진 탐색

 

이진탐색트리

 

이진탐색트리는 이진탐색을 기반으로 한 자료구조

 

- 모든 원소의 키는 유니크 하다

- 왼쪽 서브 키 값은 현재 노드 키 값 보다 값이 작다

- 오른쪽 서브 키 값은 현재 노드 키 값 보다 값이 크다

- 왼쪽, 오른쪽 서브 트리 모두 이진탐색트리다

 

이진탐색트리

 

그럼 코딩테스트에서 이진탐색은 어떨까?

 

- 단골 알고리즘중 하나로 가급적이면 외우는 것 추천!

- 단독으로 나오기 보단 다른 알고리즘과 함께 사용

- 데이터 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제 접근