검색 알고리즘

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용

 

배열에서 검색하기

1. 선형검색: 무작위로 늘어서 있는 데이터 모임에서 검색을 수행함.
2. 이진검색: 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행함.
3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행함.

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

 

선형 검색

 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.
이를 ‘선형 검색(linear search)’ 또는 ‘순차 검색(sequential search)’이라함.

선형 검색에서 배열 검색의 종료 조건은 2개이다.

1. 검색 실패: 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우.
2. 검색 성공: 검색할 값과 같은 요소를 발견한 경우.

요솟수가 n인 배열 a에서 값이 key인 요소를 검색하는 코드는 다음과 같다.

int i = 0;

while (true) {
    if (i == n) return -1; // 검색 실패
    if (a[i] == key) return i; // 검색 성공
    i++;
}