[알고리즘] Binary Search

괄괄이·2023년 9월 18일

알고리즘 이진검색

알고리즘 이론

목록 보기

2/9

✔ 이진 검색

내가 찾을 범위를 반으로 줄여가면서 빠르게 검색을 수행

이진 검색을 하기 위해서 자료가 정렬된 상태여야 한다!!

→ 문제에서 데이터가 정렬되어 있다는 조건이 없다면 반드시 정렬을 먼저 수행

🌐 검색과정
1. 자료의 중앙에 있는 원소 선택
2. 중앙 원소의 값과 목표 값 비교
3. 목표가 중앙 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색 수행
4. 목표 값을 찾을 때까지 위 과정을 반복

이진 검색 - 반복문

슈도코드

binarySearch(n, S[], key)
low <- 0
high <- n - 1

WHILE low <= high
	mid <- low + (high - low) / 2
   
   IF S[mid] == key
   	RETURN mid
   ELIF S[mid] > key
   	high <- mid - 1
   ELSE
   	low <- mid + 1
   
 RETURN -1

파이썬 코드

arr = [2, 4, 7, 9, 11, 19, 23]
arr.sort()

def binarySearch(target):
	low = 0
   high = len(arr) - 1
   
   # low > high 라면 데이터를 못찾은 경우
   while low <= high:
   	mid = (low + high) // 2
       
       # 1. 가운데 값이 정답인 경우
       if arr[mid] == target:
       	return True
       # 2. 가운데 값이 정답보다 작은 경우
       elif arr[mid] < target:
       	low = mid + 1
       # 3. 가운데 값이 정답보다 큰 경우
       else:
       	high = mid - 1
           
  	return False

이진 검색 - 재귀호출

파이썬 코드

arr = [2, 4, 7, 9, 11, 19, 23]
arr.sort()

# 함수 한 번 호출할 때마다 low, high, 변수가 바뀌어서 사용됨
def binarySearch(low, high, target):
	# 기저 조건 : 언제까지 재귀호출을 반복할 것인가?
   # low > high라면 데이터를 못찾음
   if low > high:
   	return -1 
   
   mid = (low + high) // 2
   # 1. 가운데 값이 정답인 경우
   if arr[mid] == target:
   	return mid
   # 2. 가운데 값이 정답보다 작은 경우
   elif arr[mid] < target:
   	return binarySearch(mid + 1, high, target)
   # 3. 가운데 값이 정답보다 큰 경우
   else:
   	return binarySearch(low, mid - 1, target)
           
  	return False