Binary Search에 대해 설명해보세요

---

Binary Search란?

• 이진 탐색이라고 하며, 배열 안의 데이터들이 정렬되어 있는 상태일 경우 빠른 속도로 탐색이 가능한 기법이다. 중간 원소를 기준으로 원하는 데이터와 비교하며 탐색 범위를 절반씩 좁혀가면서 탐색한다.

---

이진 탐색의 작동 방식

• 이진 탐색은 위치를 나타내는 3개의 변수를 사용한다. 배열의 맨 앞부분(시작점), 배열의 맨 끝부분(끝점), 그리고 그 중간부분(중간점)이다.

  1. 중간점과 찾고자 하는 데이터를 비교한다.

  2. 중간점이 더 작다면 시작점을 중간점으로 옮기고,더 크다면 끝점을 중간점으로 옮긴 후 중간점을 다시 지정해준다.

  3. 데이터를 찾을 때까지 반복한다.

  ---

  이진 탐색의 특징

  • 정렬된 배열에서만 사용이 가능하다.

  • 단계마다 연산 횟수가 반씩 줄어들기 때문에 O(logN)의 시간 복잡도로 빠른 성능을 가진다.

  • 구현하기 간단하다.

  ---

  결론

  이진 탐색은 정렬된 배열에서 사용가능한 데이터 탐색 방법입니다. 찾고자 하는 데이터와 배열의 중간값의 크기를 비교하면서 찾기 때문에 반드시 정렬되어 있어야 합니다. 매 단계마다 탐색하는 배열의 크기를 절반씩 줄여나가기 때문에 O(logN)의 시간 복잡도를 가집니다. 따라서 배열이 정렬되어 있다면 순차 탐색과 같은 다른 탐색 방식보다 훨씬 좋은 성능으로 탐색이 가능합니다.