[java] 이진 탐색 알고리즘
이진 탐색 알고리즘은 정렬된 배열에서 특정 값을 찾는 데 사용되는 알고리즘입니다. 배열을 반으로 나누어 탐색 범위를 좁혀가면서 원하는 값이 있는지 확인하는 방식으로 동작합니다. 이 알고리즘은 매우 효율적이며, 배열의 크기에 비해 많은 탐색을 수행할 수 있습니다.
알고리즘 원리
이진 탐색 알고리즘의 원리는 다음과 같습니다:
- 탐색 범위의 시작 인덱스를 left, 끝 인덱스를 right로 정의합니다.
- 중간 인덱스 mid를 계산합니다. mid = (left + right) / 2.
- 탐색 범위의 중간 요소와 찾으려는 값을 비교합니다.
- 만약 중간 요소가 찾으려는 값과 같다면, 검색을 종료하고 해당 인덱스를 반환합니다.
- 만약 중간 요소가 찾으려는 값보다 작다면, 탐색 범위를 오른쪽으로 좁혀 mid + 1을 새로운 left로 설정합니다.
- 만약 중간 요소가 찾으려는 값보다 크다면, 탐색 범위를 왼쪽으로 좁혀 mid - 1을 새로운 right로 설정합니다.
- left가 right보다 작거나 같은 동안 위의 과정을 반복합니다. 검색 범위가 없어질 때까지 탐색을 계속합니다.
예제 코드
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int target = 5;
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index " + result);
}
}
}