이진검색

ㅎㅎ·2021년 4월 6일
0

algorithm 개념

목록 보기
2/3

Algorithm?

: 어떤 문제를 해결하기 위한 절차의 집합

이진검색

: 범위가 한 항목으로 좁아질때 까지 항목을 포함하기 있는 리스트를 반으로 나누는 과정을 반복함.

  • 정렬된 리스트에서 원하는 항목을 찾기에 효율적인 알고리즘.

이진검색을 사용하는 방법

  1. min =1 ,max=n으로 두기
  2. max와 min의 평균을 구하되, 정수가 되도록 내리기.
  3. 추측이 많으면 끝내기. 숫자를 찾음!
  4. 추측값이 너무 작으면 min을 추측값보다 1크게 설정하기.
  5. 추측값이 너무 크면 max를 추측값보다 작게 설정.
  6. 2단계로 돌아가기.

이진 검색 실행 시간

  • n개의 요소가 있는 배열에서 선형탐색을하면 최대 n번의 탐색을 거쳐야함. 따라서 배열의 길이가 증가할수록 선형 탐색과 이진 탐색의 속도 격차는 더더욱 벌어짐.
  • 길이가 8인 배열은 이진탐색 최대 4, 길이가 16인 배열은 이진탐색 최대 5 즉, 배열이 두 배 커질때마다 최대탐색회수가 1늘어남.
  • n이 2의 제곱일때 , 최대(최악의) 이진 검색 알고리즘 실행 시간을 계산하는 방법은 n이 128이라면 이진 검색은 최대 8(2를 밑으로 하는 128의 로그 + 1)이다.
  • 만약 n이 2의 제곱이 아니라면, n다 낮은 가장 가까운 2의 제곱인 수를 고르면 된다. 만약이 길이가 1000이라면, 1000에서 낮은 가장 가까운 2의 제곱인 512(2의9승)이 된다.

0개의 댓글