[Java/Algorithm]선형검색과 보초법

 

선형검색(순차검색)
Linear search

이렇게 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 차례로 검색합니다.

0

1

2

3

4

첫번째 인덱스 0→1 →2 →3 →4 순서대로 검색합니다.

한마디로 아래 내용처럼 반복문(for, while)을 이용해 하나씩 차례로 검색하는 걸 말합니다.

---

종료조건

책에 나온 내용에서 요솟수를 입력하는 부분을 바꿔서 코드를 짜보았습니다.

1. 검색 실패 : 찾는 값이 없어 배열의 끝까지 모두 검색한 경우
2. 검색 성공 : 찾는 값을 발견한 경우

for문으로 바꾸면 좀 더 간결해집니다.

---

무한 루프

위의 while(true) 혹은 for ( ; ; ) 와 같이 무한 루프를 사용하더라도
return 혹은 break; 을 통해 빠져나올 수 있습니다.

 

---

보초법
Sentinel method

• 선형검색의 종료 조건 두가지 중 검색할 값이 없는 경우를 없애
• 종료 조건을 하나로 만드는 방법입니다.
• 검색을 시작하기 전, 찾고자 하는 값을 배열의 끝에 저장합니다.
  → 이 값을 바로 보초Sentinel 라고 합니다.