[Unifox] - 이진 탐색

동아리 시간에 배운 탐색 알고리즘에 대해 작성하려 한다.

---

이진 탐색은 탐색하려는 범위를 둘로 나누어서 탐색하는 방법이다.

업다운게임이라고 생각하면 편하다.

 

어느 정렬된 배열이 있다고 했을 때, 일반적으로 어느 값을 찾기 위해

for문과 같은 반복문을 사용하는 방법을 선택할 수 있다.

이 경우에는 찾으려는 값이 나올때 까지 하나씩 탐색하기 때문에,

시간복잡도가 O(n)이다.

n이 몇억만 되어도 시간이 꽤 걸리기 때문에 백준에서 이런 탐색법은 쓰기 어렵다.

 

배열이 정렬되어 있다는 전제 하에, 이진 탐색 알고리즘을 사용하면

시간복잡도를 O(log_2*n)으로 줄일 수 있다.

약 43억개의 원소를 가진 배열도 32번 남짓의 연산으로 커버 가능하다.

 

비록 탐색하려는 배열이 정렬되어있어야 한다는 점이 약간 걸리지만

굉장히 효율적인 알고리즘 같다고 생각한다.

 

구현도 매우 간단하다.

 

1. 탐색하려는 범위의 중간값을 찾는다.

2-1. 중간값이 찾으려는 값과 같다면 종료한다.

2-2. 중간값이 찾으려는 값보다 크다면 중간값 기준 오른쪽의 범위에서 다시 탐색한다.

2-3. 중간값이 찾으려는 값보다 작다면 중간값 기준 왼쪽의 범위에서 다시 탐색한다.

 

위의 이 코드를 구현만 하면 아주 간단하게 이진 탐색 알고리즘을 짤 수 있다!

---

탐색 알고리즘도 정렬 알고리즘처럼 정말 기본적이고 필수적인 알고리즘인 것 같다.

열심히 공부하도록 하자!

---