이진 탐색은 정렬된 배열 또는 리스트에서 특정한 항목을 찾는 알고리즘으로, 매우 효율적인 탐색 방법 중 하나이다. 이진 탐색은 데이터를 반으로 나누어 탐색 범위를 절반씩 줄여나가는 방식으로 동작한다.
동작 원리
-
탐색 범위의 중간 항목을 선택한다.
-
중간 항목과 찾고자 하는 값을 비교한다.
-
중간 항목이 찾고자 하는 값과 일치하면 탐색 성공이다.
-
중간 항목이 찾고자 하는 값보다 작으면 중간 항목의 오른쪽에 있는 부분 배열에서 탐색을 계속한다.
-
중간 항목이 찾고자 하는 값보다 크면 중간 항목의 왼쪽에 있는 부분 배열에서 탐색을 계속한다.
-
탐색 범위가 더 이상 없을 때까지 위 과정을 반복한다.
시간 복잡도
이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄이므로 시간 복잡도는 O(log n)이다. 이는 매우 효율적인 탐색 알고리즘 중 하나로, 큰 데이터셋에서도 빠르게 탐색할 수 있다.
구현 예시
아래는 이진 탐색을 자바로 구현한 예시 코드이다.
// 이진 탐색 알고리즘을 구현한 두 가지 방법을 보여주는 코드
// 반복문을 이용한 이진 탐색 구현
public static int binarySearch(int arr[], int target) {
// 배열의 가장 왼쪽 인덱스를 나타내는 변수 left를 0으로 초기화
int left = 0;
// 배열의 가장 오른쪽 인덱스를 나타내는 변수 right를 배열의 길이 - 1로 초기화
int right = arr.length - 1;
// left가 right보다 작거나 같을 때까지 반복
while(left <= right){
// 중간 지점을 계산
int mid = (left + right) / 2;
// 중간 지점이 타겟과 같으면 중간 지점의 인덱스를 반환
if(target == arr[mid]){
return mid;
}
// 타겟이 중간 값보다 작으면 오른쪽을 줄임
else if(target < arr[mid]){
right = mid - 1;
}
// 타겟이 중간 값보다 크면 왼쪽을 줄임
else{
left = mid + 1;
}
}
// 탐색 실패 시 -1을 반환
return -1;
}
// 재귀 호출을 이용한 이진 탐색 구현
public static int binarySearch2(int[] arr, int target, int left, int right) {
// 왼쪽 인덱스가 오른쪽 인덱스보다 크면 탐색 실패로 -1을 반환
if(left > right){
return -1;
}
// 중간 지점을 계산
int mid = (left + right) / 2;
// 중간 지점이 타겟과 같으면 중간 지점의 인덱스를 반환
if(target == arr[mid]){
return mid;
}
// 타겟이 중간 값보다 작으면 왼쪽 부분에 대해서 재귀 호출
else if(target < arr[mid]){
return binarySearch2(arr, target, left, mid - 1);
}
// 타겟이 중간 값보다 크면 오른쪽 부분에 대해서 재귀 호출
else{
return binarySearch2(arr, target, mid + 1, right);
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};
System.out.println("Index: " + binarySearch(arr, 30));
System.out.println();
System.out.println("Index: " + binarySearch2(arr, 30, 0, arr.length - 1));
}java에서 제공하는 binarySearch
public static void main(String[] args) {
int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};
System.out.println("== 데이터가 있는 경우 ==");
System.out.println(Arrays.binarySearch(arr, 1)); // 0
System.out.println(Arrays.binarySearch(arr, 10)); // 3
System.out.println(Arrays.binarySearch(arr, 30)); // 5
System.out.println("== 데이터가 없는 경우 ==");
System.out.println(Arrays.binarySearch(arr, 3)); // -3
System.out.println(Arrays.binarySearch(arr, 11)); // -5
System.out.println(Arrays.binarySearch(arr, 35)); // -7
}java에서 제공하는 binarySearch에서 데이터가 존재하지 않는 경우의 반환 값
-
만약 배열에 찾고자 하는 값이 존재하지 않는다면, - 부호와 함께 그 값을 찾을 수 있는 위치의 음수값을 반환한다.
-
이 값은 찾고자 하는 값이 배열에 존재하지 않을 때, 그 값이 들어갈 위치를 의미한다.
-
반환값은 - (insertion point) - 1 형태로 나타난다.
-
여기서 insertion point는 새로운 값이 들어갈 위치를 나타낸다. 따라서 insertion point - 1이 데이터가 삽입될 위치가 된다.
-
예를 들어, 배열 {1, 2, 5, 10, 20, 30, 40, 50, 60}에서 값 3을 찾는 경우, 반환값은 -3이다. 이는 값 3이 배열에 삽입될 위치가 3번 인덱스(0부터 시작)임을 나타낸다. 따라서 insertion point - 1인 3 - 1 = 2가 반환된다.
-
마찬가지로 값 11을 찾는 경우에는 -5가 반환되고, 값 35를 찾는 경우에는 -7이 반환된다.
요약
이진 탐색은 정렬된 배열에서 빠르게 항목을 찾는 효율적인 알고리즘이다. 시간 복잡도가 O(log n)이기 때문에 매우 큰 데이터셋에서도 빠르게 탐색할 수 있다. 이진 탐색은 반드시 정렬된 배열에서만 사용할 수 있으며, 배열의 중간 값을 기준으로 탐색 범위를 반으로 줄여가며 탐색을 수행한다.
