이진 탐색 또는 이분 탐색이라고 불리는 이 탐색법은,
정렬된 배열
에서특정 값
을 찾는 알고리즘을 의미한다.
이진 탐색은 배열의 중간 요소를 확인하여 찾고자 하는 값이 중간 요소보다 큰 지 작은 지 판단한다.
찾고자 하는 값이 중간 요소보다 작으면, 중간 요소 왼쪽의 절반을 탐색하고,
찾고자 하는 값이 중간 요소보다 크면, 중간 요소 오른쪽의 절반을 탐색한다.
이진 탐색은 탐색 범위를 절반 씩 줄여
나가기 때문에, 선형 탐색(Linear Search)에 비해 빠른 속도를 보장한다.
하지만, 배열이 정렬되어 있어야 한다
는 조건이 필요하기 때문에, 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요하다.
자세한 작동 과정은 아래와 같다
- 배열의 가운데 요소를 확인한다.
- 가운데 요소가 원하는 값과 일치하면 해당 요소의 인덱스를 반환한다.
- 가운데 요소가 원하는 값보다 크면, 배열의 왼쪽 절반에서 탐색을 계속한다.
- 가운데 요소가 원하는 값보다 작으면, 배열의 오른쪽 절반에서 탐색을 계속한다.
- 원하는 값을 찾을 때까지 1~4단계를 반복한다.
- 검색 범위가 더 이상 없을 때까지 원하는 값을 찾지 못한 경우, 값이 배열에 없다고 판단하여 -1 또는 적절한 오류 코드를 반환한다.
배열의 길이를 n
이라고 했을 때, 이진 탐색의 시간 복잡도는 이다.
이진 탐색은 정렬된 배열에서 빠르게 값을 찾을 수 있기 때문에, 입력 배열이 크더라도 효율적인 시간을 보여준다.
이진 탐색은 매 반복마다 배열을 반으로 나누어 탐색하기 때문에, 선형 탐색에 비해 적은 비교 횟수로 원하는 값을 찾을 수 있다.
앞서 언급했듯이, 이진 탐색은 정렬된 배열에서만 사용할 수 있다.
정렬되지 않은 배열에서 이진 탐색을 사용하려면 먼저 정렬을 해야 하는데,
이 때, 정렬에 소요되는 시간이 추가적으로 필요하므로, 탐색 전에 정렬을 수행해야 하는 경우 이진 탐색의 효율성이 상대적으로 감소할 수도 있다.
이진 탐색은 배열과 같이 임의 접근이 가능한 데이터 구조에서만 사용할 수 있다.
즉, 연결 리스트와 같은 순차 접근 데이터 구조에서는 이진 탐색을 사용하려면 비효율적일 수 있다.
이진 탐색은 중복된 값을 가진 배열에서 특정 값의 첫 번째 또는 마지막 인덱스를 찾는 데 추가적인 처리가 필요하다.
이 경우에는, 처음부터 끝까지 배열을 탐색해 중복된 값의 첫 번째 인덱스를 찾아내는 선형 탐색이 더 적합할 수 있다.
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
FIND RIGHT INTERVALS 문제에 도움 되는 쏙쏙 개념 정리 아주 굳이에용👍🔥👊