이분 탐색

이분 탐색 / 이진 탐색 알고리즘은 탐색하는 범위를 줄여나가며 원하는 값을 탐색하는 알고리즘

• 배열을 완전 탐색하는 알고리즘(brute force)은 상황에 따라 다르지만, o(N) 보다 크거나 같은 시간복잡도를 가진다.

• 하지만 이분 탐색(binary search)을 이용하여 해당 배열을 탐색하는 경우의 시간복잡도는 o(log N) 이다.

• 따라서, n이 커지면 커질 수록. 즉 배열의 크기가 커지면 커질수록 이분 탐색이 완전 탐색보다 훨씬 빠르다.

• 성능은 이분 탐색이 정말 좋긴한데, 하지만 쓸 수 있는 상황들이 제한되어있다.

• 오름차순이나 내림차순으로 배열이 “정렬” 되어 있어야 한다.