Study | 자료구조 이진 탐색

자료구조 이진 탐색

목차

1. 이진탐색이란?
2. 이진탐색의 시간복잡도

1. 이진탐색이란?

• 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘

• 열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 함

  

• 이진 탐색 과정 : 중간값과 찾으려는 값의 대소를 비교한 뒤 탐색 범위를 반으로 줄여가며 값을 찾는 탐색 알고리즘
  • 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외
  • 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값들은 탐색에서 제외

2. 이진탐색의 시간복잡도

• 운이 좋으면 찾고자 하는 값이 중간값과 동일해서 탐색이 끝남

• 최악의 경우 남은 데이터가 하나가 될 때까지 탐색을 반복함

  예시

  전체 데이터 수가 K이라고 할 때

  1. 첫 번째 탐색 후 절반만 남아 남은 수 : K/2개
  2. 두 번째 탐색에서 다시 절반만 남아 남은 수 : K/2 X 1/2 개
  3. 세 번째 탐색에서 다시 절반이 남아 남은 수 : K/2 X 1/2 X 1/2개 N) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수 : (1/2)ⁿ X K

  + 최악이 경우 (1/2)ⁿ X K = 1이 될 때까지 탐색하게 됨(= 시간복잡도 : O(log₂K)

---

출처

이진 탐색
이진 탐색 과정