스터디 시작한지 이주째.
이번 스터디 과제는 '탐색'파트 개념복습하고 해당범위
백준 풀어보는 거다.
순차탐색
탐색방법 중에 가장 간단하고 직접적.
->탐색의 대상이 되는 배열: list[ ]
->탐색의 범위: low 에서 high
순차탐색 알고리즘
int seq_search (int key, int low, int high)
{
int i;
for (i=low; i <= high; i++)
if (list[i] ==key)
return i; //탐색에 성공하면 키 값의 인덱스 반환
return -1; //탐색에 실패하면 -1 반환
}개선된 순차탐색
-
리스트 전체를 탐색하기 위한 반복문에서 리스트의 끝을 테스트하는 비교 연산
-
반복문 안에 키 값의 비교 연산
int seq_search2(int key, int low, int high)
{
int i;
list (high+1)=key;
for(i=low; list[i] !=key; i++) //키값을 가지면 종료
;
if(i==(high+1)) return -1; //탐색 실패
else return i;
}
순차탐색의 시간 복잡도
탐색에 성공: (n+1)/2번 비교
탐색에 실패: n번 비교
정렬된 배열에서의 탐색
정렬된 배열에서의 이진 탐색
이진탐색에서는 비교될때마다 탐색범위가 줄어든다.
순환호출을 이용하는 이진탐색 알고리즘
search_binary(list, low, high):
middle //low와 high 사이의 중간위치
if(탐색값==list[middle])
return middle;
else if (탐색값 < list [middle])
return list[0]부터 list [middle-1]에서의 탐색;
else if (탐색값 > list[middle])
return list[middle+1]부터 list[high]에서의 탐색;
근데 벨로그로 코드 짤때마다 생각하는건데,
벨로그도 비주얼스튜디오 만큼 코드 이상하면 에러 표시 뜨면 좋겠다..
중간중간에 영어 알파벳 하나씩 빼먹고 가는데 놓친다ㅠ
순환호출 이용 이진탐색 코드
int search_binary(int key, int low, int high)
{
int middle;
if (low <= high) {
middle= (low+high)/2;
if (key == list[middle]) //탐색 성공
return middle;
else if (key<list[middle]) //왼쪽 부분리스트 탐색
return search_binary (key, low, middle-1);
else //오른쪽 부분리스트 탐색
return search_binary(key, middle+1, high);
}
return -1; //탐색 실패
}반복 이용 이진탐색 코드
int search_binary2 (int key, int low, int high)
{
int middle;
while (low <=high) { //아직 숫자 남아있으면
middle = (low+high)/2;
if (key == list[middle])
return middle;
else if (key > list[middle])
low =middle+1;
else
high =middle-1;
}
return -1; //발견되지 않음
}
정렬된 배열에서의 색인 순차 탐색
색인 순차 탐색
(indexed sequential search)
: 인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법
-
인덱스 테이블에서 index[i] <= key < index[i+1] 을 만족하는 항목을 찾는다.
-
주 자료 리스트에서 순차 탐색 수행
장점: 빠른 시간안에 원하는 항목 발견 가능
->파일처리, 데이터베이스,,,사용구조체 선언#define INDEX_SIZE 256
typedef struct
{
int key;
int index;
}itable;
itable index_list[INDEX_SIZE];
- index 필드:리스트의 인덱스값 저장
- key 필드: 인덱스가 가리키는 곳의 키값이 저장
> 색인 순차탐색 코드
//INDEX_SIZE: 인덱스 테이블의 크기, n은 전체 데이터의 수
int search_index(int key, int n)
{
int i, low, high;
// 키 값이 리스트 범위 내의 값이 아니면 탐색 종료
if (key <list[0] || key > list [n-1])
return -1;
// 인덱스 테이블을 조사하여 해당키의 구간 결정
for (i =0; i <INDEX_SIZE; i++)
if (index_list[i].key <= key &&
index_list[i+1].key >key)
break;
if (i==INDEX_SIZE) { // 인덱스 테이블의 끝이면
low = index_list[i-1]. index;
high=n;
}
else{
low=index_list[i].index;
high=index_list[i+1].index;
}
//예상되는 범위만 순차 탐색
return seq_search(key,low, high);
}
색인 순차 탐색 복잡도
인덱스 테이블의 크기m
주자료 리스트 크기n이라하면
색인 순차 탐색 복잡도:O(m+n/m)다
보간탐색
근데 나 날이 갈 수록 벨로그 기능 하나씩 깨닫는 거 같다 히히
