*Search

정의

- 원하는 데이터를 탐색하는 것

순차검색 (Linear search)

• 맨 앞에서 맨 끝까지 순서대로 탐색을 진행하는 알고리즘
• 검색할 리스트의 길이가 길면 비효율적이다.
• 단순하고 구현이 쉽다.
• 정렬되지 않는 리스트에서도 사용할 수 있다.
• 평균 검색 횟수
  > 맨 앞에서 찾을 수 도 있고, 맨 끝까지 가서 찾을 수도 있다. 따라서 평균 검색 횟수는 (n+1)/2 이다

이진검색 (Binary search)

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
• 중간의 값을 임의의 값으로 선택하여, 찾는 값과 중간값을 비교하는 방식
• 검색이 반복될 때마다 찾는 값을 찾을 확률이 두 배가 되므로 속도가 빠르다.

피보나치 검색