CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.
핵심 개념
- 이진 탐색
- 중간값
이진 탐색
-
자료를 절반으로 나눈 후 찾는 값이 어느 쪽에 있는지 파악해 탐색범위를
반으로 줄여나가는 탐색 알고리즘
효율성과 비효율성
- 버블,삽입,선택 정렬 등의 정렬 방법은 이진 탐색을 구현하는데 유용함
- 이진 탐색의 기본은 정렬된 배열을 만들 수 있다는데 가정을 두고 있음.
(이진탐색 의사코드)
(이진탐색예시)
- 최소값을 배열의 첫 번째 값(1), 최대값을 배열의 마지막 값(63)으로 정함
- 중간값을 계산.
- 네 번째 값(29)이 될 수도 있고 다섯 번째 값(63)이 될 수도 있음.
- 어떤 값을 정하던 알고리즘은 일관적이기 때문에 상관은 없다
- 29를 중간값으로 사용했을 때, 왼편에 있는 값은 살펴볼 필요가 없다
- 50은 29보다 크기 때문에
- 최소값은 중간값 오른편에 있는 38로 정해지고 최대값은 남겨둔 후 같은 방식으로 진행
이진 탐색 vs 선형 탐색
-
이진 탐색은 일반적으로 선형탐색보다 탐색 속도가 짧으나 배열을 정리하는 시간이 추가됨
-
배열을 여러 번 탐색할 계획을 하고 있다면 이진 탐색이 유용함
-
의사코드를 수행해보면 찾고자 하는 값이 최소값보다 작거나 최대값보다 크면
해당 원소가 배열 안에 없다는 것을 알수 있음.
Comments