이진탐색

정의

이진탐색(Binary Search)은 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 이진탐색은 리스트의 중간값과 찾고자 하는 값의 크기를 비교하여 찾고자 하는 값이 중간값보다 작은 경우 중간값의 왼쪽 리스트에서 검색을 수행하고, 찾고자 하는 값이 중간값보다 큰 경우 중간값의 오른쪽 리스트에서 검색을 수행합니다. 이 과정을 반복하여 원하는 값을 찾습니다.

언제 사용?

이진 탐색은 정렬된 배열에서 원하는 값을 찾는 알고리즘이기 때문에, 배열 내에서 특정 값에 대한 검색이나 값의 존재 여부를 판단할 때 매우 유용합니다.
따라서 이진 탐색을 적용하기 위해서는 입력으로 주어진 데이터가 정렬되어 있어야 합니다. 이때, 정렬 알고리즘의 시간 복잡도는 O(n log n)입니다.
그리고 이진 탐색은 분할 정복 알고리즘의 일종이므로, 입력 데이터의 크기가 크고 탐색 범위가 넓을수록 성능상 이점이 있습니다.
따라서 이진 탐색은 배열 내에서 특정 값에 대한 검색이나 값의 존재 여부를 판단할 때, 이외에도 최댓값이나 최솟값을 찾는 문제, 특정 조건을 만족하는 값을 찾는 문제 등에서 적용 가능합니다.
하지만 이진 탐색은 배열이 정렬되어 있어야 하므로, 정렬이 어려운 경우나 입력 크기가 작을 경우에는 다른 알고리즘이 더 효율적일 수 있습니다.