바이너리 서치 개요

라이너서치는 처음부터 차근차근 1부터 n개까지 탐색하기때문에 느리다 데이터를 극단적으로 1억개까지늘리면 1억번 탐색해야한다

바이너리서치는 사전검색을 생각해보면 k로 시작하는 단어를 찾을 때는 처음 a부터 찾지않는다
대충 중앙부터 펼친뒤 k보다 뒤면 앞을, 앞이면 뒤를 본다

구현해보자

사전에서 알수잇듯이 검색할 자료는 일단 오름차순 정렬이 되어있어야한다

1. 시작인덱스와 끝인덱스를 설정
2. 시작인덱스가 끝인덱스보다 크면 종료
- 중간인덱스설정 (시작 + 끝) / 2
- 중간인덱스 값이 찾을 값과 같으면 인덱스 반환 후 함수종료

- 중간 인덱스 값이 찾을 값보다 크면 추측을 너무 높게 잡은 것이니 이 인덱스 이후부터는 볼 필요가 없다
따라서 중간인덱스를 끝인덱스 - 1로 설정
- 반대로 낮으면 같은 로직으로 시작인덱스 + 1로 설정
3. 못찾으면 운지 리턴


100개 자료에서 찾을때마다 반틈씩 잘려나간다
100 50 25 13 7 3 1  약 7번

1억건이라도 대충 30번이면 찾는다

라이너서치처럼 탐색시간이 확늘어나지 않는다

로그함수와 같이 탐색횟수가 완만한형태를 가진다
log100 = 약 7
log50 = 6
log25 = 5
log13 = 4
...