이진 탐색 (Binary Search) 및 파생 개념

이진 탐색(Binary Serach) 정의

 

참고 링크 : www.youtube.com/watch?v=W7RGHiN0Mmw&t=96s

 

1) 저장된 값을 정렬한다.  

2) 왼쪽 = 첫번째 값 / 오른쪽 = 맨 마지막에 위치한 값 / 중간값 = 그 중간의 값

3) 중간값과 원하는 값의 차이에 따라 탐색하는 값의 범위를 변경해 나간다. 

(ex : 원하는 값이 중간값보다 크다 -> 왼쪽 = 중간값 + 1

원하는 값이 중간값보다 작다 -> 오른쪽 = 중간값 -1)

4) 원하는 답이 나올때까지 3번의 과정을 반복한다

 

이진 탐색(혹은 이분 탐색, 이분 검색)은 탐색 기법 중 하나이며, 원하는 값을 탐색 범위를 두 부분으로 분할하여 찾는 방식이다. 

단, 이미 오름차순 혹은 내림차순으로 정렬된 구조에서 사용 가능하다는 조건이 있다. 

순차탐색과 달리 탐색 범위를 좁혀가며 찾아가는 방법이기 때문에 시간 복잡도는 O(log n) 이다.

(기존 순차 탐색의 시간 복잡도 : O(n)) 

 

* 전제조건은 '원하는 값'이 이미 정해져 있어야 한다는 사실이다. 

---

이진 탐색 구현 방식

 

크게 3가지 방식이 있다. 

• 반복문으로 구현
• 재귀호출로 구현
• 기존 STL을 활용

구체적인 구현 방식 및 설명은 하단에 기입된 블로그를 참고해보자.

 

https://blog.naver.com/PostView.nhn?blogId=3246902&logNo=221921485735&from=search&redirect=Log&widgetTypeCall=true&topReferer=https%3A%2F%2Fsearch.naver.com%2Fsearch.naver%3Fsm%3Dtab_hty.top%26where%3Dpost%26query%3Dc%252B%252B%2BSTL%2Bbinary%2Bsearch%26oquery%3Dbinary_search%2Bc%252B%252B%26tqi%3DUVNqvdprvN8ssPCR1NCsssssti8-434225&directAccess=false

[알고리즘] 이분(이진) 탐색 (Binary Search) - 정의, 소스코드, 예제

 

---

파라메트릭 탐색(Parametric Search) 정의

 

이진 탐색의 경우, 원하는 값이 정확히 정해져있다는 특징이 있지만 (ex : 7)

간혹 구체적인 값이 정해지지 않고 오로지 조건만 정의되는 경우가 있다. 

이 경우 사용하는 방식이 파라메트릭 탐색이다.(*Parametric : 매개 변수의)

 

구체적인 구현 방식 및 설명은 하단에 기입된 블로그를 참고해보자. 

 

https://sarah950716.tistory.com/16

[이분탐색] 파라메트릭 서치(개념)