binary search

Binary search

• 정렬된 리스트에서 가운데를 기준으로 찾는 값이 더 작을 경우 왼쪽으로 큰경우 오른쪽으로 범위를 줄여가면서 찾아가는 알고리즘.
• 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만, 검색범위가 절반으로 줄기 때문에 속도가 빠르다.

시간 복잡도 $O(logn)$