[집합과 검색] #2. 검색 알고리즘

검색

검색과 키

검색	특정 항목에 주목하는 것.
키	검색이 주목하는 특정 항목

배열에서의 검색

1. 배열 검색
2. 선형 리스트 검색
3. 이진 검색 트리 검색

선형 검색

요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 처음부터 순서대로 요소를 검색하는 방법.

선형검색

배열 검색의 종료 조건

• 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
• 검색할 값과 같은 요소를 발견한 경우

보초법

검색에서 반복 시, 종료 조건은 다음과 같다.

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

이 조건은 단순한 판단이라고 하나, 검색 횟수가 많을수록 종료 조건을 검사하는 비용은 기하급수적으로 증가한다.

이러한 비용을 반으로 줄이는 방법이 보초법이다.

보초: 검색하기 전에 검색하고자 하는 값을 맨 끝 요소에 저장한 값.

 

보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 수행한다.

 

보초법

다시 말해, 검색 시 찾기 원하는 값을 배열의 맨 마지막 요소로 저장하고(ㄱ) 선형 검색을 시도한다.

이때 검색할 값과 같은 원소를 발견하면 검색을 종료하고 검색할 값과 같은 보초(ㄱ)를 찾으면 검색이 실패한 것이다.

 

이는 while() 문으로 완성할 수 있는데,

1. 해당 인덱스의 값이 검색할 값과 같은 경우: 검색 성공 및 종료
2. 모든 인덱스의 순회가 이루어진 경우(현재 인덱스의 값 == 검색 횟수): 검색 실패 및 종료

결국 보초법을 이용하면 종료 조건이 "검색할 값과 같은 요소를 발견한 경우"만 판단하면 되므로 조건비교에 따른 시간을 단축시킬 수 있다.

이진 검색

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

(단, 데이터가 키 값으로 이미 정렬되있다는 조건을 가진다.)

 

이진 검색을 한 단계 진행할 때마다 검색 범위가 (거의)반으로 좁혀짐에 따라 불필요한 비교를 줄일 수 있다.

 

이진 검색의 초기화

LOW	검색 범위의 맨 앞 인덱스
MID	검색 범위의 중앙 인덱스
HIGH	검색 범위의 맨 끝 인덱스

이진 검색의 종료 조건

1. 중앙인덱스의 값과 KEY가 같은 경우
2. 검색 범위가 더 이상 존재하지 않는 경우

이진 검색

만약 위의 배열에서 76(KEY)을 찾는다고 가정하자. 이때의 배열은 정렬되어있다.
이진 검색의 순서는 다음과 같다.

1. LOW:2 , MID = 47, HIGH:94 를 판단하며 KEY값과 비교를 한다.
2. MID < KEY 이므로, LOW ~ MID는 검색 대상에서 제외한다.
3. LOW:51 , MID =77, HIGH:94 를 판단하며 KEY값과 비교를 한다.
4. MID > KEY 이므로,  MID ~ HIGH는 검색 대상에서 제외한다.
5. LOW:51 , MID =64, HIGH:76 를 판단하며 KEY값과 비교를 한다.
6. MID < KEY 이고 비교대상이 더이상 없으므로 값을 판단 후 종료한다.