이진 탐색(Binary Search)

정렬된 리스트에서 값을 찾는 효율적인 방법

절반씩 나눠가며 값을 찾아서 O(log n)의 빠른 알고리즘

 

1.먼저 리스트 가운데 값을 찾음

2.찾고자 하는 값이 가운데 값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 본다.

3.위 과정을 계속 반복

 

리스트의 크기가 클 수록 성능이 빛을 발함.

100만개의 항목 중 값을 찾으려 할 때 최대 20번 비교만으로 찾을 수 있음