선형 검색과 보초법

선형 검색(Linear Search)

• 배열에서 검색하는 방법 중 가장 기본적인 알고리즘

• 순차 검색(Sequential Search)라고도 함

• 원하는 값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 검색하는 방법

• 검색할 값을 찾지 못하고 배열의 맨 끝을 지나면 검색 실패, 원소를 찾으면 성공

보초법

매 반복시마다 선형 검색은 두번의 검사를 거친다.

1. 배열의 끝을 지났는지
2. 찾는 원소가 있는지

이러한 부분은 배열의 길이가 짧다면 무시할 수 있겠지만, 길다면 무시할 수 없는 비용이 든다. 이러한 연산량을 절반으로 줄일 수 있는 방법이 보초법이다.

보초법을 수행하는 방법은 다음과 같다.

1. 찾는 key값과 동일한 보초 key를 배열 마지막에 추가한다.
2. 종료 조건을 key값을 만났을때만으로 줄인다.

다만 key값을 만났을 때 이것이 정말 찾는 key인지 보초 key인지 확인하는 연산을 1회 추가해야함
ex) return False if i == len(arr) else i