히비스서커스의 블로그

검색알고리즘을 공부하며 정리해보았다. 검색 검색에 있어서 키란 찾는 항목을 말한다. 종류 검색의 종류는 크게 3가지 배열검색, 연결리스트검색, 이진검색트리검색 등이 있다. 여기서, 배열검색에는 선형 검색, 이진 검색, 해시법 등이 존재한다. 선형검색 선형검색이란 (1xn)의 모양으로 늘어진 배열에서 검색할 때 원하는 키를 맨 왼쪽에서 맨오른쪽으로 한 칸씩 이동하며 찾는 검색방법이다. 선형검색의 종료조건은 크게 2 가지가 있다. 1. 배열에서 키 값을 가진 원소를 못찾고 지나간 경우 (검색에 실패한 경우) 2. 배열에서 키 값을 가진 원소를 찾은 경우 (검색에 성공한 경우) 배열의 개수가 n이라면 조건을 판단하는 횟수는 평균 n/2이다. 선형검색을 수행하면 배열의 매 원소를 지나갈 때마다 1번과 2번을 확..