이진 탐색이란?
이진 탐색(binary search)이라는 말 그대로 탐색하는 방법중 하나인데 순차 탐색과는 다르게 정렬된 데이터 집합을 이분화하면서 탐색하는 것이다.
예를들면, 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우가 있다.
[그림 8-5]의 정렬된 데이터 집합에서 이진 탐색을 이용해 데이터 15를 탐색하는 과정을 살펴보자.
① 중간에 위치한 데이터인 11과 찾고자 하는 15가 같은지 비교한다.
② 중간에 위치한 데이터인 11보다 찾고자 하는 데이터인 15가 크므로 중간 데이터 11의 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.
③ 탐색 영역의 중간에 위치한 데이터인 17과 찾고자 하는 15가 같은지 비교한다.
④ 중간에 위치한 데이터인 17보다 찾고자 하는 데이터인 15가 작으므로 중간 데이터 17 왼쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.
⑤ 탐색 영역의 중간에 위치한 데이터인 15와 찾고자 하는 15가 같은지 비교한다. 원하는 데이터이므로 탐색을 종료한다.
[네이버 지식백과] 이진 탐색 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))
내가짜본
이진탐색 소스(c언어)
이진탐색의 장점과 단점
-장점 : 이진탐색 방법은 순차탐색처럼 하나하나 일일히 값을 확인하지 않고 효과적으로 원하는 값을 찾아낼 수 있다.
-단점 : 배열이 반듯히 정렬되어 있어야 한다는 제약이있다.
'C언어 > 예제 및 소스' 카테고리의 다른 글
C언어 :: malloc 함수를 이용한 동적할당 예제 (2) | 2015.04.13 |
---|---|
C언어 :: 큐 구현 소스 ! (0) | 2015.04.12 |
C언어 :: 스택 구현 소스 및 보고서 (1) | 2015.04.12 |
C언어 :: 달팽이 배열 소스 ! (1) | 2015.04.12 |
C언어 :: 버블정렬과 선택정렬 알고리즘 & 구현 소스 (1) | 2015.04.12 |
WRITTEN BY
,