🖥️ CS/Data Structure & Algorithm

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

한국의 메타몽 2020. 5. 22. 10:57

이진 탐색(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) - 정의, 소스코드, 예제

이분 탐색 (Binary Search) 정의이분 탐색(이진 탐색)은 탐색 기법 중 하나이며 원하는 탐색 범위를 두 ...

blog.naver.com

 


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

 

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

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

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

 

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

 

https://sarah950716.tistory.com/16

 

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

파라메트릭 서치 문제는 단독 문제로 나오기보다는 다른 알고리즘과 결합해서 출제되는 것 같습니다. 파라메트릭 서치는 간단히 말하자면, (갓종만북의 표현을 빌려) 최적화 문제(문제의 상황��

sarah950716.tistory.com

 

'🖥️ CS > Data Structure & Algorithm' 카테고리의 다른 글

map  (0) 2020.10.15
플로이드 와샬 알고리즘  (0) 2020.09.28
동적 계획법 (Dynamic Programming)  (0) 2020.04.22
백 트래킹 (Back Tracking)  (0) 2020.03.15
stable_sort() 그리고 sort()  (0) 2020.03.13