TIL | 1.2.월 [CS 기초지식 | 이분 탐색 / 이진 탐색]

- 이분 탐색 

 

이분탐색(=이진 탐색)이란?

• 데이터 탐색 방법 중 하나로 

내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다.

반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값들은 탐색에서 제외된다.

정리하면 중간값과 찾으려는 값의 대소를 비교한 뒤 탐색 범위를 반으로 줄여가며 값을 찾는 탐색 알고리즘이다.

 

---

이분 탐색 | 시간 복잡도

중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문에 배열을 전수 조사하는 O(N)에 비해 훨씬 빠른 O(logN)이다.