정렬된 배열

2장 알고리즘이 중요한 까닭

1. 정렬된 배열 orderred array: 값이 항상 순서대로 존재하는 배열 삽입할 때는 항상 삽입 전에 값의 올바른 위치를 찾고, 다른 값들을 옮겨 공간을 만들어야 한다. O(N) 삽입에 필요한 단계 수는 새 값이 정렬된 배열 어디에 놓이게 되든 비슷하다 앞 부분에 삽입할 경우, 비교가 줄어들고 이동이 늘어남 뒷 부분에 삽입할 경우, 비교가 늘어나고 이동이 줄어듬 2. 정렬된 배열의 검색 선형 검색: 앞에서부터 검색 이 경우 시간복잡도는 O(N)이다. 그러나 더 나은 방법이 있다… 3. 이진 검색(이진 탐색, Binary Search) 1에서 100 사이의 업다운 게임을 생각해 보자. 50, 25, 13… 찾는 값의 범위는 절반의 절반의 절반으로 줄어든다. 4. 이진 검색 대 선형 검색 작은 크기의..