탐색

탐색을 위한 자료 구조 : 배열, 연결 리스트, 트리, 그래프 등 다양함

 

정렬되지 않은 배열에서의 탐색

순차 탐색 : 가장 간단하고 직접적인 탐색 방법으로, 데이터의 양이 많으면 비효율적임

 

int search(int key, int low, int high){
	int i;
	for(i=low; i<=high; i++)
		if(list[i]==key)
			return i;
	return -1;
}

 

정렬된 배열에서의 탐색

이진 탐색 : 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분의 배열에 있는지를 알아내여 탐색의 범위를 반으로 줄어나가는 과정

 

int main(){
	int n, i, key, lt=0, rt, mid, tmp;
	scanf("%d %d", &n, &key); //배열의 크기와 탐색할 값 key 입력받기
	vector<int> a;
	for(i=0; i<n; i++){
		scanf("%d", &tmp);
		a.push_back(tmp);
	}
	sort(a.begin(), a.end()); //(정렬되지 않은 상태에서) 오름차순 정렬
	rt=n-1;
	while(lt<=rt){
		mid=(lt+rt)/2;
		if(a[mid]==key) {
			printf("%d\n", mid+1);
			return 0;
		}
		else if(a[mid]>key) rt=mid-1;
		else lt=mid+1;
	}
	return 0;
}