(CS50)-알고리즘 기초(이진탐색)

CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.

그림출처

핵심 개념

• 이진 탐색
• 중간값

이진 탐색

• 자료를 절반으로 나눈 후 찾는 값이 어느 쪽에 있는지 파악해 탐색범위를

  반으로 줄여나가는 탐색 알고리즘

효율성과 비효율성

• 버블,삽입,선택 정렬 등의 정렬 방법은 이진 탐색을 구현하는데 유용함
• 이진 탐색의 기본은 정렬된 배열을 만들 수 있다는데 가정을 두고 있음.

(이진탐색 의사코드)

(이진탐색예시)

• 최소값을 배열의 첫 번째 값(1), 최대값을 배열의 마지막 값(63)으로 정함
• 중간값을 계산.
  • 네 번째 값(29)이 될 수도 있고 다섯 번째 값(63)이 될 수도 있음.
  • 어떤 값을 정하던 알고리즘은 일관적이기 때문에 상관은 없다
• 29를 중간값으로 사용했을 때, 왼편에 있는 값은 살펴볼 필요가 없다
  • 50은 29보다 크기 때문에
• 최소값은 중간값 오른편에 있는 38로 정해지고 최대값은 남겨둔 후 같은 방식으로 진행

이진 탐색 vs 선형 탐색

• 이진 탐색은 일반적으로 선형탐색보다 탐색 속도가 짧으나 배열을 정리하는 시간이 추가됨

• 배열을 여러 번 탐색할 계획을 하고 있다면 이진 탐색이 유용함

• 의사코드를 수행해보면 찾고자 하는 값이 최소값보다 작거나 최대값보다 크면

  해당 원소가 배열 안에 없다는 것을 알수 있음.