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

📌 이분 탐색 (Binary Search)이란?

---

정렬되어 있는 배열에서 전체 원소 중 찾고자 하는 원소 N이 있는 지 탐색하는 방법 중 하나입니다. 앞에서부터 끝까지 탐색하는 선형 탐색과는 다르게 정렬되어 있는 점을 활용하여 원소의 중간부분부터 탐색을 시작하는 이분 탐색은 선형 탐색보다 시간에서 유리한 점을 갖습니다.

📌 반복자 이용하여 이분탐색 구현하기

---

보통 PS를 위해서 구현하는 인덱스를 이용한 방법과는 다르게 c++ 표준 라이브러리 함수와 반복자를 이용했기 때문에 배열 인덱스 사용 위험이 없습니다.

📌 인덱스 이용하여 이분탐색 구현하기

---

정렬되어 있는 배열에서 특정한 값이 존재하는 지, true or false를 반환하는 이분 탐색 함수입니다.

📌 이분 탐색 (Binary Search) 분석

---

전체 원소 범위를 반 씩 나누면서 탐색하기 때문에 수행할 때 마다 N/2, N/4, N/8 과 같이 줄어듭니다. N -> 1이 되는 과정 까지 총 logN 번 수행합니다. 따라서 이분 탐색의 시간 복잡도는 O(logN)입니다.

📌 마무리

---

정렬되어 있는 배열 내에서 원소를 찾을 때, 선형 시간 보다 빠르게 찾을 수 있는 알고리즘인 이분 탐색 알고리즘에 대해 배워보았습니다. 정렬되어 있는 수 중에서 특정 원소를 찾을 때에도 사용되지만, 필요에 따라서 정렬되어 있는 배열에서 적절한 N값을 찾아내기 위한 parametric search에도 사용됩니다.