이분 탐색 #Binary Search [ 수정 내역 ] [ 수정 ]

최근 수정: 6년 전

1. 개요

Binary Search.

정렬되어 있는 리스트에서 특정 값을 빠르게 찾는 알고리즘. 시간복잡도는 O(logN).

제일 중요한 것은 정렬이 되어 있어야 한다는 것이다. 따라서 아무 때나 적용하다간 정렬하는데에 시간이 더 오래 걸릴 수 있으므로 주의. 하지만 이미 정렬이 되어 있다면 굉장한 속도로 탐색이 가능하다.

2. 상세

리스트의 중간에 있는 값을 뽑아서 찾고자 하는 값과 비교. 같다면 탐색 종료. 찾고자 하는 값이 더 작으면 중간의 왼쪽 부분, 크면 중간의 오른쪽 부분을 탐색한다.