<목차>
ㅇ
ㅇ
ㅇ
ㅇ 검색 알고리즘
- 특정 원소를 검색
ㅇ 시퀀셜 서치
- 우리가 했던 방식! 반복문으로 0번째부터 끝까지 돌면서 찾는 방식
- 원소의 정렬이 필요 없지만 리스트 길이가 길면 비효율적
- 시간 예측 불가능
- 0부터 5천만 번까지 다 검색해야 할 수도 있어
- 근데 첫번째에 나올 수도 있어
ㅇ 바이너리 서치. 이진 탐색
- 바이너리 서치 춤 ㅋㅋㅋㅋㅋㅋㅋ 링크
- 리스트의 중간 값을 정해 크고 작음을 비교해 검색하는 알고리즘
- 정렬된 리스트에 사용할 수 있다.
- 처음부터 끝까지 다 체크하는 건 아니니까 속도는 빠른데, 대신 정렬 해야 해
- 힌트1 : 5와 7 비교해서 7이 더 크면 그 밑의 수들은 볼 필요 없어!! => 로우 인덱스 갱신
- 힌트2 : 운 좋으면 가운데 있어서 한번에, 또는 계속 해서 최종 2개까지 남을 수 있어. 언제 끝날지 모르니까 => while이 적합
(내 풀이)
- 수정1 :while의 조건을 못 찾아서 우선 트루로 들어오고 브레이크 걸었었는데 => (로우<하이)인 동안에 하면 되는 거였음!
- 수정2 : 맥락이 if문을 실행한 뒤 새로운 mid값을 찾는 거니까 mid=(low+high)/2가 맨 아래 있는 게 더 알맞아!
(쌤 풀이)
STEP BY STEP