Algorithm?
: 어떤 문제를 해결하기 위한 절차의 집합
이진검색
: 범위가 한 항목으로 좁아질때 까지 항목을 포함하기 있는 리스트를 반으로 나누는 과정을 반복함.
- 정렬된 리스트에서 원하는 항목을 찾기에 효율적인 알고리즘.
이진검색을 사용하는 방법
- min =1 ,max=n으로 두기
- max와 min의 평균을 구하되, 정수가 되도록 내리기.
- 추측이 많으면 끝내기. 숫자를 찾음!
- 추측값이 너무 작으면 min을 추측값보다 1크게 설정하기.
- 추측값이 너무 크면 max를 추측값보다 작게 설정.
- 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승)이 된다.