이진 검색 (Binary Search)

이진 검색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 검색 알고리즘 중 가장 효율적인 알고리즘 중 하나입니다.

 

이진 검색의 동작과정은 다음과 같습니다.

1. 배열의 중간 요소를 선택합니다.
2. 중간 요소의 값과 검색할 값의 크기를 비교합니다.
3. 검색할 값이 중간 요소보다 작으면 중간 요소의 왼쪽 부분 배열에서 검색을 수행합니다.
4. 검색할 값이 중간 요소보다 크면 중간 요소의 오른쪽 부분 배열에서 검색을 수행합니다.
5. 검색할 값이 중간 요소와 일치하면 검색을 종료합니다.

아래는 이진 검색의 동작 과정을 나타낸 그림입니다.

이진 검색의 시간 복잡도는 검색할 배열의 크기가 n일 때, 최악의 경우에는 log2(n) 번의 비교를 수행하므로 O(log n)입니다.

 

따라서, 이진 검색은 큰 배열에서도 효율적으로 검색을 수행할 수 있습니다.