26.05_이진 탐색 알고리즘_22.09.27

탐색 알고리즘

>3총사

• 선형 알고리즘
• 이진 탐색 알고리즘
• 해시 탐색 알고리즘

 

이진 탐색 알고리즘, Binary Search Algorithm

>의미

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

: 흔히 알고 있는 업앤다운 처럼 검색하는 방법

>탐색 과정

1. 중간 지점 확인

2. 중간 지점이 원하는 결과면 종료, 아니면 3번 진행

3. 결과값이 중간 지점보다 윗 범위에 속하는 지, 아랫 범위에 속하는지 확인

// 이 확인 과정이 가능해야 이진 탐색 알고리즘을 사용할 수 있겠다.

4. 결과값이 속한 범위의 중간 지점확인. 즉, 1번부터 다시 반복

>단점

: 배열에서만 구현 가능

: 배열이 정렬되어 있어야만 사용 가능

=>정렬되지 않은 배열을 정렬시키고 이진 탐색 알고리즘을 사용하는 것은 효율이 떨어짐.

>사용 예시

: 대규모 데이터 검색에 주로 사용

//사전 검색, 도서관 도서 검색 등

: 대규모 시스템에 대한 리소스 사항 파악
//시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU 양에 대해서 파악할 때 사용

: 반도체 테스트 프로그램은 디지털, 아날로그 레벨을 측정하는데 Binary Search Algorithm을 사용

 

//이진 탐색 트리랑 이름 비슷하다고 헷갈리지 말기