이진 탐색 알고리즘

순차탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

>시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

1. 시작점[0]-중간점[4]-끝점[9] (소수점 이하 제거)
2. 시작점[0]-중간점[1]-끝점[3]
3. 시작점[2]-중간점[2]-끝점[3] (탐색 완료)

단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횐수는 log2N에 비례

초기 데이터 개수 32개

1단계 이후 16개

2단계 이후  8개

3단계 이후  4개

>따라서 시간복잡도 O(log N)