Search Algorithm
- 탐색은 기억 공간에 저장된 데이터나 주어진 입력 데이터 집합에서 어떤 조건이나 성질을 만족하는 데이터를 찾는 것을 말한다.
- 탐색은 정렬된 데이터 집합에서 찾는것과 정렬되지 않은 집합에서 찾는 경우로 구분할수 있는데 정렬된 데이터 집합에서 찾는 이진 탐색과 정렬되지 않은 집합에서 찾는 선형 탐색 알고리즘을 알아보자.
- 선형 탐색(linear search)은 순차 탐색(sequential search)이라고도 하는데, 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하면서 찾는 방법이다.
- 첫 번째 데이터인 15와 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다.
- 두 번째 데이터인 11과 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다.
- 세 번째 데이터인 1과 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다.
- 네 번째 데이터인 3과 찾고자 하는 3이 같은지 비교하는데, 같으므로 원하는 데이터를 찾고 탐색을 종료한다.
- 이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다.
- 중간에 위치한 데이터인 11과 찾고자 하는 15가 같은지 비교한다.
- 중간에 위치한 데이터인 11보다 찾고자 하는 데이터인 15가 크므로 중간 데이터 11의 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.
- 탐색 영역의 중간에 위치한 데이터인 17과 찾고자 하는 15가 같은지 비교한다.
- 중간에 위치한 데이터인 17보다 찾고자 하는 데이터인 15가 작으므로 중간 데이터 17 왼쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.
- 탐색 영역의 중간에 위치한 데이터인 15와 찾고자 하는 15가 같은지 비교한다. 원하는 데이터이므로 탐색을 종료한다.
