순차탐색과 이분탐색

탐색이란?

탐색이란 데이터 구조 안의 저장된 정보를 찾는 것입니다.
대표적인 탐색 알고리즘에는 3가지가 있습니다.

• 순차탐색 (Sequential Search)
  혹은 선형탐색 (Linear Search)
• 이분탐색 (Binary Search)
• 해시탐색 (Hash Search)

이 글에서는 순차탐색과 이분탐색만을 다룹니다. 해시탐색은 언젠가 다룰 예정...

순차탐색 (Sequential Search)

순차탐색은 탐색알고리즘 중 가장 간단한 형태의 알고리즘이며,
선형탐색 (Linear Search) 라고도 합니다.
어떠한 데이터 배열이 있으면 데이터 배열의 처음부터 끝까지 모두 비교하여 자료를 찾아냅니다.

쉽게 말해서 그냥 배열 처음부터 끝까지 노가다.

장점

• 정렬되지 않은 배열에서 사용할 수 있다.
• 구현이 간편하다.

단점

• 데이터의 양이 많아지면 비효율적이다.

순차탐색의 코드는 아래와 같습니다.

위의 내용을 함수로 만든 코드 스니펫 (클릭)

이분탐색 (Binary Search)

이분탐색은 정렬된 데이터에서 쓸 수 있는 탐색 알고리즘으로,
찾고자 하는 값을 가운데 값과 비교해서 그 값이 왼쪽에 있는지 오른쪽에 있는지 파악하여 자료를 찾습니다.

장점

• 순차탐색에 비해 탐색속도가 빠르다.

단점

• 데이터가 미리 정렬되어 있어야 한다.
• 데이터의 임의접근(Random Access)이 가능해야한다.
  
  데이터에 몇개의 요소가 있는지에 관계없이, 모든 요소에 대해 같은 시간 내에 접근 할 수 있는 접근 방식,
  C언어의 배열은 임의접근이 가능하며, 연결리스트와 같은 특정 자료구조는 불가능하다. (어렵다면 지금은 무시해도 좋다.)

이분탐색의 대략적인 의사코드는 다음과 같습니다..

1. 배열의 중앙값과 찾으려는 값을 비교한다.
2. 만약 찾으려는 값이 더 작다면 왼쪽 부분, 더 크다면 오른쪽 부분을 선택한다. 같다면 탐색을 종료한다.
3. 선택한 구간의 중앙값과 찾으려는 값을 비교한다. -> B로 돌아간다.

이분탐색은 재귀함수와 반복문, 두 가지 방법으로 구현할 수 있습니다.

이분탐색의 반복문 구현

위의 내용을 함수로 만든 코드 스니펫 (클릭)

이분탐색의 재귀함수 구현

위의 내용을 함수로 만든 코드 스니펫 (클릭)