[자료구조] : 검색(이진검색, 선형검색, 해시법) (C)

출처 | DO IT C언어 자료구조(입문)

이번 시간에는 이진검색, 선형검색, 해시법에 대한 얘기를 하겠다.

1. 국적이 한국인 사람을 찾는다.
2. 나이가 21세 이상 27세 미만인 사람을 찾는다.
3. 어떤 낱말과 발음이 가장 비슷한 이름의 사람을 찾는다.

• 우리는 주소록을 검색한다고 가정하면, 어떤 검색을 하게 되더라도 특정 항목에 주목한다는 점은 검색하기의 공통점이다.
• 여기서 주목하는 것이 키(key)라고 얘기하겠다.
• 국적을 검색하는 경우 국적이 키고, 나이를 검색하는 경우 나이가 키다.
• 데이터가 단순한 정수 값이면, 데이터 값을 키 값이라고 생각해도 좋지만 대부분의 경우는 키는 데이터의 일부다. 그런데 위 예시를 보면, 키 값을 아래와 같이 진행한다.

1. 키 값과 일치하도록 지정한다.(일본)
2. 키 값의 구간을 지정한다.(21세 이상 27세 미만)
3. 키 값과 비슷하도록 지정한다.(발음이 비슷한 사람)

일반적인 자료구조에서 검색에 대한 세 가지 예가 존재한다.

1. 선형검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다.
   

2. 이진 검색
   

3. 해시법 : 추가, 삭제가 자주 일나는 데이터 모임에서 빠른 검색을 수행한다.(체인법, 오픈 소스법)

• 해시법
  • 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
  • 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법