순차 탐색(sequential search)

요소가 직전 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 찾을 때까지 앞부터 순서대로 탐색하는 알고리즘

🎈순차 탐색의 종료 조건

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우

위 사진은 while문과 for 문 두 경우로 작성된 요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색하는 알고리즘이다.

🔑 i == n이 성립하는 경우
: 검색 실패이므로 -1 반환 (종료 조건 1)

🔑 a[i]==key가 성립하는 경우
: 검색 성공이므로 i를 반환 (종료 조건 2)

보초법

순차 탐색은 반복할 때마다 종료 조건 2가지를 모두 판단한다. 데이터가 방대할 경우 비용과 시간이 많이 걸릴 수 있으므로 보다 효율적인 순차탐색 알고리즘이다.

🎈 보초법?

기존에 있는 배열 끝에 찾고자 하는 데이터의 값을 가진 인덱스를 하나 추가한다. 이 때 이 값을 보초(sentinel)이라고 한다.

만약 위 그림에서 5를 검색해야한다고 했을 때 원래의 데이터에 5가 있지 않아도 보초 값에 5가 들어가 있기 때문에 기존에 있던 순차탐색의 종료 조건 1개를 줄일 수 있다.

while 문의 종료 조건이 1개임을 볼 수 있다.

reutn i == n ? -1 : i;

🧐 while문에 의한 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단하는 삼항연산자이다. 변수 i 값이 n이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환한다.