📚 상식 퀴즈 해설

Q. 다음 중 가장 빠른 검색 알고리즘은?

제시된 보기 중 가장 효율적인 검색 알고리즘은 이진 검색(Binary Search)입니다. 이진 검색은 정렬된 데이터에서 중간값을 기준으로 탐색 범위를 절반씩 줄여나가므로, 시간 복잡도가 O(log n)입니다. 예를 들어 100만 개의 데이터에서 최대 약 20번의 비교만으로 원하는 값을 찾을 수 있습니다. 반면 선형 검색(Linear Search)은 처음부터 끝까지 하나씩 확인하므로 O(n)의 시간이 걸려, 100만 개라면 최악의 경우 100만 번 비교해야 합니다. 이진 검색의 전제 조건은 데이터가 이미 정렬되어 있어야 한다는 것입니다. 일상생활에서 이진 검색의 원리를 활용하는 예로 사전에서 단어 찾기가 있습니다. 사전을 중간쯤 펼쳐서 찾는 단어가 앞인지 뒤인지 판단하고, 해당 방향으로 다시 중간을 펼치는 과정을 반복하는 것이 이진 검색과 같은 원리입니다.