1. 정렬된 배열

• orderred array: 값이 항상 순서대로 존재하는 배열
• 삽입할 때는 항상 삽입 전에 값의 올바른 위치를 찾고, 다른 값들을 옮겨 공간을 만들어야 한다.
• O(N)
• 삽입에 필요한 단계 수는 새 값이 정렬된 배열 어디에 놓이게 되든 비슷하다
  • 앞 부분에 삽입할 경우, 비교가 줄어들고 이동이 늘어남
  • 뒷 부분에 삽입할 경우, 비교가 늘어나고 이동이 줄어듬

2. 정렬된 배열의 검색

• 선형 검색: 앞에서부터 검색
• 이 경우 시간복잡도는 O(N)이다.
• 그러나 더 나은 방법이 있다…

3. 이진 검색(이진 탐색, Binary Search)

• 1에서 100 사이의 업다운 게임을 생각해 보자.
  • 50, 25, 13… 찾는 값의 범위는 절반의 절반의 절반으로 줄어든다.

4. 이진 검색 대 선형 검색

• 작은 크기의 정렬된 배열이라면 이진 검색이 선형 검색보다 크게 나은 점이 없다.
• 그러나 배열이 더 커지면?
• 100개의 값을 가진 배열에서 검색에 필요한 최대 단계 수
  • 선형 검색: 100
  • 이진 검색: 7 (100에 log 2를 취한 값)
• 즉, 데이터의 양이 2배로 늘어날 때마다 이진 검색은 최대 한 단계만 더 추가된다.
• 200개의 값을 가진 배열에서 검색에 필요한 최대 단계 수
  • 선형 검색: 200
  • 이진 검색: 8 (100에 log 2를 취한 값)

5. 마무리

• 어떤 문제를 푸는 방법은 대개 둘 이상 존재하며, 사용자가 선택하는 알고리즘이 코드의 속도에 크게 영향을 줄 수 있다.
• 정렬된 배열의 검색은 매우 효율적이지만, 검색이 자주 필요하지 않고, 데이터를 추가하기만 한다면 삽입을 더 빠르게 처리하는 배열이 나은 선택일 수 있다.
• 즉, 상황에 따라 어떤 자료구조를 선택하느냐가 기량을 가른다.