09-02 이진 탐색(Binary Search)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.이진 탐색(Binary Search)

 1)정의

 -정렬된 데이터에서 특정한 값을 찾아내는 알고리즘.

 -탐색 범위를 반으로 나누어 찾는 방식으로 값을 포함하는 범위를 줄여가는 방식.

  -이진 탐색은 사용될 때마다 범위 대상의 크기가 절반으로 줄어든다.

 2)작동 과정

 

       -데이터 중앙에 있는 요소를 고르고 목표값과 비교.

 

 

   -목표 값이 중앙 요소 값보다 작다면 중앙을 기준으로 데이터 왼 편에 대해, 크다면 오른 편에 대해 이진 탐색을 수행

 

-원하는 값을 찾을 때까지 반복

 

 

 

2.이진탐색 트리 성능 측정

 1)최대 반복횟수 수식

  -데이터 크기를 n, 탐색 반복 횟수를 x라고 한다면 탐색 완료 시점에서 데이터 범위의 크기는 1은 n에

  1/2의 x제곱을 곱한 값이다.

 

 -이것을 로그함수로 표현하면

3.이진탐색 알고리즘 구현

 1)데이터 및 데이터 셋

2)이진 탐색 함수

3)데이터 비교 메서드

4)테스트