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

💡 이진 탐색 (Binary Search)

👉 정렬된 상태의 데이터에서 특정 값을 빠르게 검색하는 방법

• 찾고자 하는 값과 데이터 중앙에 있는 값을 비교한다.
• 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색을 진행한다.
• 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색을 진행한다.

👉 알고리즘 시간 복잡도 : O(logn)

---

💡 이진 탐색 과정

👉 조건

• 데이터가 우선 정렬된 상태여야 이진 탐색을 진행할 수 있다.

👉 예시

• 배열 : [1, 2, 5, 10, 20, 30, 40, 50, 60]
• 찾고자 하는 데이터 : 30

1. 찾고자 하는 값과 데이터 중앙에 있는 값 20 (mid = (0+8) / 2 = 4) 을 비교한다.
2. 값이 더 크므로 데이터 오른쪽 부분에서 이진 탐색을 진행한다.
3. 찾고자 하는 값과 데이터 중앙에 있는 값 40 (mid = (0+3) / 2 = 1) 을 비교한다.
4. 값이 더 작으므로 데이터 왼쪽 부분에서 이진 탐색을 진행하면 30을 찾을 수 있다.