[알고리즘] 이진 탐색(Binary Search)

이진 탐색

💡 아이디어

배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색해보자!!

⭐단, 배열 내 데이터는 이미 정렬되어 있어야 한다.⭐

 

 

💡 알고리즘 설명

1. 탐색하고자 하는 범위(start, end)를 정한다. 
2. start와 end 사이 mid를 정한다. 
3. mid의 데이터와 찾으려는 데이터를 비교한다. 
   1) 같을 경우
       - 탐색을 종료한다. 
   2) 중간점의 데이터가 더 클 경우 
       - end를 (mid - 1)로 설정해 mid의 왼쪽을 탐색한다. 
   3) 중간점의 데이터가 더 작을 경우
       - start를 (mid + 1)로 설정해 mid의 오른쪽을 탐색한다. 
4. start와 end 사이에 데이터가 존재하는 동안 2~3의 과정을 반복한다. 

 

출처: https://www.geeksforgeeks.org/binary-search/

 

 

💡 소스 코드

다음은 array 내의 target의 인덱스를 찾아서 반환하는 함수이다. 

 

- 재귀함수로 구현한 이진 탐색

def binarySearch(array, target, start, end):
  if start > end:
    return None

  mid = (start + end) // 2

  if array[mid] == target:
    return mid
  elif array[mid] > target:
    return binarySearch(array, target, start, mid - 1)
  else:
    return binarySearch(array, target, mid + 1, end)

 

- 반복문으로 구현한 이진 탐색

def binarySearch2(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

 

 

💡 코딩 테스트에서의 이진 탐색

코딩 테스트에서의 이진 탐색 문제는 주로 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다. 따라서 탐색 범위가 2000만을 넘어가면 이진 탐색을 떠올려보자! 

 

참고로 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 알고리즘을 떠올려야 하는 경우가 많다. 

 

이진 탐색 문제를 풀 때, 많~~~은 입력 데이터를 input()으로 받으려 하면 시간 초과로 오답 판정을 받을 수 있다. 이럴 땐 sys 라이브러리의 readline() 함수를 이용하면 input() 보다 빠르게 입력을 받을 수 있다. 그런데 사실 데이터 크기가 어느 정도일 때 써야 하는지는 아직 감이 안 온다..!😥

 

# 빠르게 입력 받기
import sys
input = lambda: sys.stdin.readline().rstrip()
data = list(map(int, input().split()))
print(data)

 

 

 

 

 

 

 

참고 자료: 이것이 취업을 위한 코딩 테스트다 with Python (나동빈 저, 한빛미디어)