탐색 리스트: 하나 이상의 필드로 된 레코드의 집합 키(key): 레코드를 구분하기 위해서 사용되는 필드 순차 탐색 template int SeqSearch(E *a, const int n, const K &k) { // a[1:n]을 왼쪽에서 오른쪽으로 탐색 // a[i]의 키 값이 k와 같은 가장 작은 i를 반환, 없으면 0 반환 int i; for (i = 1; i n) return 0; // i값을 찾지 못한 경우 return i; // i값을 찾은 경우 } 시간복잡도 - O(n) 순차 탐색의 성능 향상(정렬된 리스트의 경우) SepSearch의 for 조건 부분을 i n을 i > n || a[i] != k로 변경 탐색이 실패할 때 성능 향상 이원 탐색(Binary Search) int Binar..

이원 탐색 이미 정렬된 배열 a[0] ... a[n-1]에서 x=a[j]인 j를 반환 - left, right: 탐색하고자 하는 리스트의 왼쪽, 오른쪽 끝 - 초기값 left = 0, right = n-1 - 리스트의 중간 위치 middle = (left/right)/2 - a[middle]과 x 비교 1) x right = middle-1 2) x = a[middle] -> middle 반환 3) x > a[middle] -> left = middle+1 int BinarySearch(int *a, const int x, const int n) { // 정렬된 배열 a[left], ..., a[right]에서 x 탐색 int left = 0, right = n - 1; whi..