1. 검색 알고리즘
1-1. 검색과 키
검색 알고리즘 : 원하는 값을 가진 요소를 찾아내는 알고리즘
키 (key) : 검색할 때, 주목하는 항목 / 데이터의 일부
❗️검색시 조건은 하나만 지정하기도 하지만, 복합해서 지정하기도 함.
2. 배열 검색
3. 선형 검색 (순차 검색)
요소가 직선모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색.
- 0번 요소를 선택, 일치하는 값이 없다.
- 1번 요소를 선택, 일치하는 값이 없다.
- 2번 요소를 선택, 일치하는 값이 없다.
- 3번 요소를 선택, 일치하는 값을 찾았다. 검색성공!
❗️다만, 위의 배열에서 '5'를 찾으면 배열에 없는 값인 것 처럼.
배열을 끝까지 검색했지만 검색에 실패할 수 있다.
검색종료조건
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색실패)
- 검색할 값과 같은 요소를 발견한 경우 (검색성공)
3-1. 선형 검색 프로그램 구현하기
배열a의 처음부터 끝까지 n개요소를 대상으로 값이 key인 요소를 선형검색하고 검색한 요소의 인덱스를 반환하는 프로그램. 요소가 존재하지 않으면 -1을 반환합니다.
3-2. 보초법
선형검색은 반복할 때마다 종료조건을 판단한다.
때문에 종료조건을 판단하기 위한 시간과 비용이 소비된다.
이를 방지하기 위해서 비용을 반으로 줄이는 '보초법'이 있다.
'보초법'을 이해하는데 시간이 조금 걸렸다.
다시한번 복습해야겠다 :)
ᴘᴇᴛɪᴛs ᴅᴇ́ᴠᴇʟᴏᴘᴘᴇᴜʀ. ᴘʀᴏɢʀᴀᴍᴍᴀᴛɪᴏɴ = ᴘʟᴀɪsɪʀ 💕