C언어 :: 이진탐색 알고리즘 & 구현 소스

이진 탐색이란?

이진 탐색(binary search)이라는 말 그대로 탐색하는 방법중 하나인데 순차 탐색과는 다르게 정렬된 데이터 집합을 이분화하면서 탐색하는 것이다.

 

예를들면, 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우가 있다.

[그림 8-5]의 정렬된 데이터 집합에서 이진 탐색을 이용해 데이터 15를 탐색하는 과정을 살펴보자.

[그림 8-5] 이진 탐색을 위한 데이터 집합

① 중간에 위치한 데이터인 11과 찾고자 하는 15가 같은지 비교한다.

② 중간에 위치한 데이터인 11보다 찾고자 하는 데이터인 15가 크므로 중간 데이터 11의 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

③ 탐색 영역의 중간에 위치한 데이터인 17과 찾고자 하는 15가 같은지 비교한다.

④ 중간에 위치한 데이터인 17보다 찾고자 하는 데이터인 15가 작으므로 중간 데이터 17 왼쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

⑤ 탐색 영역의 중간에 위치한 데이터인 15와 찾고자 하는 15가 같은지 비교한다. 원하는 데이터이므로 탐색을 종료한다.

 

[네이버 지식백과] 이진 탐색 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))

 

내가짜본

이진탐색 소스(c언어)

이진탐색의 장점과 단점

-장점 : 이진탐색 방법은 순차탐색처럼 하나하나 일일히 값을 확인하지 않고 효과적으로 원하는 값을 찾아낼 수 있다.

-단점 : 배열이 반듯히 정렬되어 있어야 한다는 제약이있다.