가장 기본적인 탐색을 직접 구현해야 이후 이진 탐색이나 해시 탐색이 왜 더 빠른지 비교할 수 있습니다. 조기 반환과 '값이 없음' 처리는 거의 모든 탐색 문제의 출발점입니다.
리스트 numbers를 앞에서부터 확인해 target이 처음 등장하는 인덱스를 반환하세요. 값이 없으면 -1을 반환합니다.
linear_search(numbers, target)
시간 O(n), 추가 공간 O(1)
실행하면 아래 순서대로 채점합니다. print() 출력도 이 순서대로 쌓입니다.
| # | 이름 | numbers | target | 기대값 |
|---|---|---|---|---|
| 1 | 중간에서 발견 | [4, 7, 1, 9] | 1 | 2 |
| 2 | 중복이면 첫 위치 | [3, 2, 3, 3] | 3 | 0 |
| 3 | 값이 없음 | [1, 2, 3] | 8 | -1 |
| 4 | 빈 리스트 | [] | 5 | -1 |
| 5 | 마지막 위치 | [5, 8, 13] | 13 | 2 |
Python 표준 라이브러리는 사용할 수 있습니다. 함수 이름과 매개변수는 제시된 형태를 유지하세요.
list)은 인덱스로 읽을 때 O(1), 처음부터 값을 찾을 때 O(n) 입니다.코드를 작성하고 실행하면 5개의 테스트가 각각 표시됩니다.