이진 검색(Binary Search)은 정렬된 데이터에서 원하는 값을 빠르게 찾는 대표적인 탐색 알고리즘입니다. 아래 예제는 Java에서 재귀(Recursion) 방식을 활용해 이진 검색을 구현한 프로그램입니다.
예제 코드
public class Demo{
int rec_bin_search(int my_arr[], int left, int right, int x){
if (right >= left){
int mid = left + (right - left) / 2;
if (my_arr[mid] == x)
return mid;
if (my_arr[mid] > x)
return rec_bin_search(my_arr, left, mid - 1, x);
return rec_bin_search(my_arr, mid + 1, right, x);
}
return -1;
}
public static void main(String args[]){
Demo my_object = new Demo();
int my_arr[] = { 56, 78, 90, 32, 45, 99, 104};
int len = my_arr.length;
int x = 104;
int result = my_object.rec_bin_search(my_arr, 0, len - 1, x);
if (result == -1)
System.out.println("The element is not present in the array");
else
System.out.println("The element has been found at index " + result);
}
}실행 결과
The element has been found at index 6
코드 설명
Demo 클래스 안에는 이진 검색을 수행하는 rec_bin_search 함수가 정의되어 있습니다. 이 함수는 배열과 함께 탐색 범위의 시작 인덱스(left), 끝 인덱스(right), 그리고 찾고자 하는 값(x)을 매개변수로 전달받습니다.
탐색 범위 내에서 중간 인덱스(mid)를 계산한 뒤, 해당 위치의 값이 찾으려는 값과 일치하면 그 인덱스를 반환합니다. 중간 값이 찾으려는 값보다 크면 왼쪽 절반을, 작으면 오른쪽 절반을 대상으로 자기 자신을 다시 호출하는 재귀 구조로 되어 있습니다. 탐색 범위가 더 이상 유효하지 않으면 값을 찾지 못했다는 의미로 -1을 반환합니다.
main 함수에서는 Demo 객체의 인스턴스를 생성하고 배열에 값을 할당합니다. 이후 검색할 특정 값을 매개변수로 넘겨 이진 검색 함수를 호출하며, 값이 발견되면 해당 인덱스를 출력하고, 발견되지 않으면 그에 맞는 안내 메시지를 화면에 표시합니다.
참고 사항
이진 검색은 원래 정렬된 배열을 기준으로 동작하는 알고리즘입니다. 위 예제의 배열은 정렬되어 있지 않지만 우연히 올바른 결과가 나왔을 뿐, 실제 프로젝트에서는 반드시 Arrays.sort() 등으로 배열을 먼저 정렬한 후 사용해야 정확한 결과를 보장할 수 있습니다.