[자바 Do It! 알고리즘]Chapter03 검색 알고리즘(검색 알고리즘, 선형검색)

여기에서 배우는 것은 배열 검색이며 다음의 알고리즘을 활용합니다.

1. 선형 검색

- 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.

2. 이진 검색

- 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.

3. 해시법

- 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다.

- 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

- 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

​

데이터 집합이 있을 때 '검색만 하면되지!'라고 생각한다면 검색에 사용할 알고리즘은 계산시간이 짧은 것을 선택하면 됩니다. 그러나 데이터 집합에 대한 검색뿐 아니라 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야 합니다. 예를 들어 데이터 추가를 자주하는 경우에는 검색이 빠르더라도 데이터의 추가 비용이 많이 들어가는 알고리즘은 피해야 합니다. 따라서 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러 가지인 경우에는 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 합니다.

​

※ 어떤 경우에 데이터 추가 비용이 더 많이 들까요?

예를 들어, 학생의 번호 순서대로 키(height)의 값을 넣은 배열이 있다고 가정할 경우 학생의 번호만 알면 바로 키(height)값을 알 수 있습니다. 하지만 새로운 학생이 전학을 와서 중간에 데이터를 끼워 넣어야 할 경우라면 이후의 학생을 모두 뒤로 밀어 넣는 작업을 해야 합니다. 바로 이런 경우에 '배열은 검색은 빠르지만 데이터를 추가하기 위한 비용이 많이 든다'라고 합니다.

​

[선형검색]

1. 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고르즘입니다.

2. 배열 검색의 종료 조건은 2개로 판단할 수 있습니다.

1번 조건 : 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우

2번 조건 : 검색할 값과 같은 요소를 발견한 경우

3. 배열의 요솟수가 n개일때 1번,2번 조건 2개를 판단하는 횟수는 평균 n/2회 입니다.

- 원하는 값이 배열에 존재하지 않는 경우 1번 조건은 n+1회, 2번 조건은 n회로 됩니다.

​

​

선형검색을 구현한 프로그램

​