Binary Search Algorithm

이진 탐색

데이터가 정렬된 상태에서 절반씩 반으로 나눠 분할 정복 기법으로 특정한 값을 찾아내는 알고리즘

 

 

동작 과정

1. 정렬된 배열의 중간 인덱스 지정 ( 그 지정 값을 pivot 이라 부름 )
2. 찾으려 하는 값과 동일하면 종료하고, 아니면 3단계로 이동
3. 찾으려는 값이 중간 인덱스의 값보다 큰지, 작은지 확인
4. pivot 보다 작은 경우 반으로 나눈 왼쪽 배열, pivot보다 큰 경우 반으로 나눈 오른쪽 배열을 선택
5. 선택한 배열에서 다시 1단계부터 반복

 

이진 탐색을 사용 하는 경우

1. 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용
2. 데이터의 양이 많으면 많을수록 효율이 높아서 정렬된 데이터의 양이 많을 때 사용

 

* 단, 항상 효율이 좋은 것은 아닙니다.

-> 데이터의 양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 선형 탐색이 더 빠릅니다.

 

 

이진 탐색의 한계

1. 정렬된 배열에서만 가능합니다.
2. 규모가 작은 배열이라도 정렬되어 있지 않다면 이진 탐색을 사용해도 효율이 낮습니다.

 

이진 탐색 사용 사례

1. 사전 검색
2. 도서관 도서 검색
3. 대규모 시스템에 대한 리소스 사항 파악
4. 반도체 기업들에서 디지털/아날로그 레벨 측정하는 경우

 

BST 와 차이점

BST는 Tree는 하나의 노드가 두개의 하위 트리를 가지는 이진트리의 자료구조를 나타냅니ㅏㄷ