해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다.
순차탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
- 시간복잡도 : O(N)
이진 탐색
- 정렬된 배열에 대해서 반으로 쪼개가며 확인하는 방법
- 시간복잡도 : O(logN)
- 구현 방법 : 반복문 or 재귀 함수
유형
" 코드를 정리하고 최대 탐색범위와 시간복잡도를 고려할 때, 연산의 수가 2000만(파이썬 평균 연산 수)를 넘어간다면
이진탐색 또는 계수 정렬 등을 고려하자. "
" 정렬되어있을 때 라는 말이 많이 나옴"
'Algorithm > Binary Search' 카테고리의 다른 글
| 가사 검색 (1) | 2023.04.12 |
|---|---|
| 고정점 찾기 (0) | 2023.04.12 |
| 정렬된 배열에서 특정 수의 개수 구하기 (0) | 2023.04.12 |
| 떡볶이 떡 만들기 (0) | 2023.04.12 |
| 부품 찾기 (0) | 2023.04.12 |
