자료구조 강의 내용

증명은 일반적이지 않다 => 하지만 증명을 함으로써 더 잘 이해할 수 있다 => 시험 문제 증명해!
 
이진 탐색의 종류 : 루프 이진 탐색, 재귀 이진 탐색

---

recursive binary search (재귀 이진 탐색)
 
ex1)

int search(int a[], int n, int x)
{
	int m;
	if (n == 0) return -1;
	m = n / 2;

	if (a[m] == x)
		return m;

	else if (a[m] > x)
		return search(a, m, x);

	else // a[m] < x
		return m + 1 + search(a + m + 1, n - (m + 1), x);
}

 
ex2) ex1을 간단하게

int search(int a[], int n, int x)
{
	int m;
	if (n == 0) return -1;
	m = n / 2;

	if (a[m] == x) return 1

	else if (a[m] > x)
		return search(a, m, x);

	else // a[m] < x
		return search(a + m + 1, n - (m + 1), x);
}

 
- 증명
주장 : 만약 어떤 i에 대하여 a[i] = x 라면 위 함수는 i를 리턴한다
Base : n = 0인 경우 "어떤 i에 대해서 a[i]는 x"가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다
Step :
Case 1 : a[m]  = x 인 경우 m을 리턴하므로 주장이 성립
Case 2 : a[m] > x인 경우 a[m]
 
 
시간 (complexity)
T(n)
 

---

selection sort (선택 정렬)
 
전체를 훑어
제일작은걸찾아
삭제하지 않고 제일 작은 걸 첫 번째
그 다음에 작은 걸 두번 째
 
 
증명
입력 : a[0], a[1], ..., a[n-1] <- (정수) 집합
 
Sorting이 완료된 후 다음이 만족되어야 함

• Sorting이 끝난 후 배열에 저장된 값들을 b[0], b[1], ..., b[n-1]라고 부른자 (같은 배열이지만 구별하기 위해서 이름만 다르게 부루는 것임)
• 조건 1 : { a[0], a[1], ..., a[n-1]} = { b[0], b[1], ..., b[n-1]} 집합으로 같음
• 조건 2 : b[0] < b[1] < ... < b[n-1]} (편의상 같은 값은 없다고 가정)

proof by invariant
집합 조건을 깰 수 있는 코드는 없음
invariant : k번째 루프가 끝난 후에

---

recursive selection sort