[이것이 코딩테스트다] 7장 이진 탐색(Binary Search)

 이진 탐색은 탐색 범위를 반으로 좁혀가면서 빠르게 탐색하는 알고리즘이다.

이진 탐색을 공부하기 위해선 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 알아야 한다.

 

<순차탐색>

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

📌 순차탐색은 주로 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.

✅ 순차적으로 target을 찾기 전까지 모든 데이터를 훑기 때문에 최악의 경우 데이터의 개수가 N개일 때 N번의 비교 연산이 이루어지므로, 시간 복잡도가 O(N)이 된다.

✅ 파이썬의 'count 메서드'는 내부적으로 순차 탐색이 수행된다.

 

1. 이진 탐색이란?

📌 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

 

✅ 이진 탐색은 시작점, 끝점, 중간점 이렇게 3가지 인덱스를 이용해 데이터를 탐색하는 알고리즘이다. 

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는다.

✅한 번 확인할 때마다 원소가 반씩 줄어드므로 시간 복잡도가 O(logN)이다.

✅탐색 범위가 큰 상황에서의 탐색을 가정하는 문제(범위 2000만 이상)는 이진 탐색을 먼저 떠올리자!

 

2. 이진 탐색 구현 방법

📌 코딩테스트에서 이진 탐색의 소스코드를 구현하는 것은 생각보다 어려울 수 있으니 자연스럽게 외우는 것을 추천한다. 

1️⃣ 재귀 함수 

def binary_search(array, target, start, end):
  if start>end:
    return None;
  mid = (start + end) // 2 
  #찾은 경우 중간점 인덱스 반환
  if array[mid] == target:
    return mid
  #중간점보다 target이 작은 경우 왼쪽 탐색
  elif array[mid]>target:
    return binary_search(array, target, start, mid - 1 ) #end를 mid-1로 설정
  #중간점보다 target이 큰 경우 오른쪽 탐색
  else:
    return binary_search(array, target, mid + 1, end) #start를 mid+1로 설정

#n(원소의 개수)와 target 입력받기
n, target = list(map(int, input().split()))
#전체 원소 입력받기
array = list(map(int, input().split()))

#이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1) #처음 값과 끝 값을 각각 start,end로 설정
if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result+1)

2️⃣ 반복문

##이진탐색-반복문
def binary_search(array, target, start, end):
  while start<=end:
    mid = (start + end) // 2
    #찾은 경우 인덱스 반환
    if array[mid] == target:
      return mid
    #중간점보다 target이 작은 경우 왼쪽 탐색
    elif array[mid]>target:
      end = mid - 1
    #중간점보다 target이 큰 경우 오른쪽 탐색
    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) #처음 값과 끝 값을 각각 start,end로 설정
if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result+1)

 

3. 예제 - 부품찾기

📌 두  개의 배열이 주어지고, 두 번째 배열 값들이 첫 번째 배열에 들어있는지 확인하는 문제이다.

#예제 - 부품 찾기 
def binary(array, target, start, end ):
  while start<=end:
    mid = (start+end)//2
    if array[mid] == target:
      return print("yes", end = ' ')
    elif array[mid] > target:
      end = mid -1
    else:
      start = mid + 1
  return print("no", end = ' ');


#입력
N = int(input())
input_array = list(map(int, input().split()))
input_array.sort() #이진 탐색을 사용하기 위해 정렬 
target_N = int(input())
target_array = list(map(int, input().split()))

for i in target_array:
  binary(input_array, i, 0, N-1)