Binary search (이진 탐색)#include int binary_search(int a[], int n, int x){ int l = 0; int r = n-1; while(l x) r = m-1; // 찾는 수가 더 작은 경우 else l = m+1; // 찾는 수가 더 큰 경우 } return -1; // ... (1)}int main(){ int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; printf("%d\n", binary_search(a, 10, 3)); return 0;}index가 있으면 index를 return 하고, 없으면 -1을 return l은 왼쪽 끝의 index, r은 오른쪽 끝의 인..

Array (배열)정의 : 연속된 주소, 동일한 타입장점 : n개 중 k번째 access가 상수 시간에 가능, Search가 빠름(경우에 따라 다를 수는 있음)단점 : 크기 변화 비용이 크다, Insert, Delete가 느릴 수 있다.사용 : 변화가 없거나 드문 자료에 사용함Linear Search (선형 검색)순서대로 전부 탐색하는 검색 방법 #include int linear_search(int a[], int n, int x){ for (int i = 0; i 찾지 못하면 -1을 return 하도록 약속함배열의 이름은 주소 : a[i] == *(a+i)O(n) Sorting이 되면 더 빨리 검색할 수 있음

수학적 귀납법수학적 귀납법의 기본형Base : P(1)이 참이다Step : P(n-1) → P(n)이 참이다 ( p→ q 형태 )Result : P(n)은 모든 자연수에 대해 참이다우리가 증명하려는 것은 전체가 참이라는 것을 보이는 것이다. 하나하나가 참인지 거짓인지는 알지 못해도 됨.그 이유는, P(n-1)이 거짓일 때는 무조건 T가 되기 때문에 P(n-1)이 참일때 전체가 참이면 무조건 P(n)은 참이다. * P : 무엇인지 모르는 것 > 이름, 명제 등* n : 자연수 ex) Prove that \(1 + 2 + 3 ... + n =  \frac{n(n+1)}{2}\) for all \(n \epsilon \mathbb{N}\)(1) Base : \(P(1) = 1 = \frac{1 \times 2..