!! 구 블로그 (Blogger) 에서 가져온 글입니다. 글 일부가 깨져보일 수 있습니다.
탐색이란?
탐색이란 데이터 구조 안의 저장된 정보를 찾는 것입니다.
대표적인 탐색 알고리즘에는 3가지가 있습니다.
- 순차탐색 (Sequential Search) 혹은 선형탐색 (Linear Search)
- 이분탐색 (Binary Search)
- 해시탐색 (Hash Search)
이 글에서는 순차탐색과 이분탐색만을 다룹니다. 해시탐색은 언젠가 다룰 예정...
순차탐색 (Sequential Search)
순차탐색은 탐색알고리즘 중 가장 간단한 형태의 알고리즘이며,선형탐색 (Linear Search) 라고도 합니다.
어떠한 데이터 배열이 있으면 데이터 배열의 처음부터 끝까지 모두 비교하여 자료를 찾아냅니다.
쉽게 말해서 그냥 배열 처음부터 끝까지 노가다.
장점
- 정렬되지 않은 배열에서 사용할 수 있다.
- 구현이 간편하다.
- 데이터의 양이 많아지면 비효율적이다.
순차탐색의 코드는 아래와 같습니다.
위의 내용을 함수로 만든 코드 스니펫 (클릭)
이분탐색 (Binary Search)
이분탐색은 정렬된 데이터에서 쓸 수 있는 탐색 알고리즘으로,찾고자 하는 값을 가운데 값과 비교해서 그 값이 왼쪽에 있는지 오른쪽에 있는지 파악하여 자료를 찾습니다.
장점
- 순차탐색에 비해 탐색속도가 빠르다.
- 데이터가 미리 정렬되어 있어야 한다.
- 데이터의 임의접근(Random Access)이 가능해야한다.
데이터에 몇개의 요소가 있는지에 관계없이, 모든 요소에 대해 같은 시간 내에 접근 할 수 있는 접근 방식,
C언어의 배열은 임의접근이 가능하며, 연결리스트와 같은 특정 자료구조는 불가능하다. (어렵다면 지금은 무시해도 좋다.)
- 배열의 중앙값과 찾으려는 값을 비교한다.
- 만약 찾으려는 값이 더 작다면 왼쪽 부분, 더 크다면 오른쪽 부분을 선택한다. 같다면 탐색을 종료한다.
- 선택한 구간의 중앙값과 찾으려는 값을 비교한다. -> B로 돌아간다.
이분탐색의 반복문 구현
위의 내용을 함수로 만든 코드 스니펫 (클릭)
이분탐색의 재귀함수 구현
