탐색(Search)

선형 탐색 알고리즘(Linear Search)

• 앞에서부터 차례대로 탐색
• 데이터가 정렬되어 있지 않을 경우 사용
• 데이터가 많을수록 비효율적
• O(n)

이진 탐색 알고리즘(Binary Search)

• 정렬 후 중간값을 기준으로 필요없는 부분을 잘라내가며 탐색
• 한번 탐색할때마다 대상이 절반(1/2)으로 줄어듬
• 데이터가 많을수록 효율적
• O(log n)
• 결정 문제에 사용 된다 -> 정답의 범위가 주어지고 이진탐색으로 좁혀나가 최적의 해를 구한다 (파라매트릭 서치)
  • 결정 문제 : YES or NO 로 답할 수 있는 문제 -> mid값이 최적의 해인가? YES

방법

1. 이분 탐색할 리스트를 정렬한다.
2. 이분 탐색 범위의 시작(left)와 끝(right)를 초기화 한다.
   • 초기 값을 잘못 설정하면 오답을 유발한다
3. mid 값을 도출해 이분 탐색 진행
4. 결과에 따라 left=mid+1 or right=mid-1해서 다음회전 진행