이진탐색 - 개념정리

Yona·2021년 9월 13일

알고리즘 이진탐색

🌻 algorithm

목록 보기

7/18

이진탐색

사용 : 탐색 범위가 큰 상황에서의 탐색

전제조건 : 데이터가 정렬되어있어야

트리 자료구조 사용해 항상 정렬 상태 유지하는것이 good

시간복잡도 : O(logN)

순차탐색

처음부터 끝까지 찾을때까지 순서대로 조회
당연히 최악의 시간복잡도는 O(N)

이진탐색

조건 : 데이터는 이미 정렬되어있어야한다. ➡️ 이진탐색트리와의 연관
필요 : 시작점, 끝점, 중간점
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터 찾기
시간복잡도 : O(logN)

ex) 정렬된 10개 데이터 중 4인 원소 찾기

index	0	1	2	3	4	5	6	7	8	9
	0	2	4	6	8	10	12	14	16	18
1회차	시작점				중간점					끝점
2회차	시작점	중간점		끝점
3회차			시작점&중간점	끝점

왜 시간복잡도는 logN일까?

간단한 컨셉 ) 한 단계를 거칠때마다 확인하는 원소가 평균적으로 절반으로 줄어듬
ex) 32 -> 16 -> 8 -> 4 -> 2
단계마다 2로 나누는 것과 동일하므로 연산횟수는 log(2)N
컴퓨터 수학에서의 log 밑은 디폴트 2니까 logN으로 표기

코드 구현

이진탐색 코드를 제대로 작성하는 사람은 의외로 적다고 한다.
코테 단골 문제이니 코드를 가급적 외울 것.

반복문 사용 버전

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

# 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) :
  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)
 

# 원소의 갯수와 찾고자하는 문자열 입력받기
n, target = list(map(int, input().split()))
#  전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
print(result)

코테에서의 이진탐색

단순해보여도 레퍼런스 없는 상태에서 통으로 구현하기 은근 까다롭다
- 외우세용
높은 난이도에서는 이진탐색 알고리즘이 다른 알고리즘과 함께 사용되기도
- 외우세용
탐색범위가 큰 상황에서의 탐색을 가정하는 문제가 많다.
- 탐색범위가 2,000만을 넘어가면 이진탐색으로 접근할 것 권한다
- 처리할 데이터 갯수가 1,000만 단위 이상으로 넘어가면 O(logN)의 속도를 내야하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우 많음