이진 탐색(Binary Search) 란?

이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.

동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

특징

: 탐색 대상 배열(또는 리스트)은 반드시 정렬되어 있어야 한다.

: 중앙 원소와 비교해 찾는 값이 적으면 왼쪽 절반만, 크면 오른쪽 절반만 다시 탐색한다.

매번 탐색 범위를 반으로 줄여간다.

: O(log n) - 매우 큰 배열에서도 빠르게 동작한다.