알고리즘 - 검색(선형검색, 이진검색)

선형검색

구분	내용
특징	처음부터 순서대로 하나씩 찾는 방식
장점	작동방식과 구현이 단순하다
단점	-모든 데이터를 조사한다 -데이터 개수에 검색시간이 비례한다 -비효율적인 방식 ex.100만개의 대상 중에서 찾는 값이 100만번째에 있다면 100만번째에 이르러서야 찾을 수 있다

 

• 알고리즘 효율

구분	내용
최대 검색횟수	O(n)
평균 검색횟수	n/2회

 

---

 

이진검색

 

이진검색은 트리구조에 대해 알고 있으면 좋다. (☞데이터구조 - 트리)

 

이진검색은 다음과 같이 이루어진다.

 

만약 '6' 의 위치를 알고자 한다. 먼저 루트노드의 값과 비교하여 좌측인지 우측인지 확인한다. 예시의 경우 오름차순이므로 찾으려는 값 6은 루트노드의 값 5보다 우측에 위치한다. 좌측은 확인할 필요가 없다. 루트노드의 우측 자식노드의 값은 7이다. 6은 7보다 작으므로 좌측 노드로 이동한다. 그리고 해당값을 찾았다.

 

 

구분	내용
특징	-검색범위를 1/2로 나눠서 찾는다 -기준이 되는 노드와 비교하여 찾을 범위를 1/2씩 줄여나간다 -검색하기 전에 데이터가 일정한 기준으로 정렬되어 있어야 이진검색방식을 적용할 수 있다 -새로운 레코드를 삽입, 삭제하는 경우 구조를 재구성해야하기 때문에 삽입, 삭제가 빈번한 경우 다른 구조를 사용하는 것이 바람직하다
장점	-모든 데이터를 검색할 필요가 없다 -데이터의 개수가 많더라도 검색에 시간이 많이 소요되지 않는다 ex. 100만개의 대상 중에서 원하는 값은 20번째 안에 찾을 수 있다. (2의 20제곱 = 1,048,576 )
단점	-정렬되지 않은 경우 사용할 수 없다 -검색은 빠르지만 정렬에 시간이 소요된다

 

• 알고리즘 효율

구분	내용
최대 검색횟수	log 2 n + 1
평균 검색횟수	log 2 n