import java.util.Arrays;
public class BinarySearchSample {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11}; // 정렬된 배열
Arrays.sort(arr); // 배열이 정렬되지 않았을 경우 사용
int target = 5; // 찾고자 하는 값
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println(target + "은(는) 배열에 없습니다.");
} else {
System.out.println(target + "은(는) 배열의 인덱스 " + result + "에 있습니다.");
}
}
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // 중간 인덱스 계산
if (arr[mid] == target) {
return mid; // 타겟을 찾았을 때
} else if (arr[mid] < target) {
low = mid + 1; // 타겟이 중간값보다 클 때
} else {
high = mid - 1; // 타겟이 중간값보다 작을 때
}
}
return -1; // 타겟이 배열에 없을 때
}
}이진 탐색 이분 탐색(Binary Search)는 정렬된 배열에서 특정 요소를 효율적으로 찾는 검색 알고리즘인데, 배열을 반으로 나눈 뒤, 탐색 범위를 절반씩 줄여나가는 방법으로 정해진 값을 찾게 된다.
코드를 통해 보자면 배열 arr을 선언하고 정렬한 다음 찾으려는 값 target을 지정해서 이진 탐색으로 target의 index를 찾는 binarySearch를 호출하게 되는데
binarySearch 메소드로 들어오면, 배열의 최소 인덱스와, 최대 인덱스를 정의해준 후 while문을 돌리면서 중간 인덱스를 찾은 후, 중간 인덱스가 target과 동일하다면 바로 인덱스를 반환해주면 끝나지만
찾지 못했을 경우에는 배열[중간_인덱스] 가 target보다 작다면 low에 mid + 1을 해주고, target보다 크다면 high에 mid – 1을 해주는 식으로 찾을 범위를 반씩 계속 줄여주면 단순 조회보다 훨씬 빠르게 target이 배열의 몇 번째 인덱스에 있는지 찾아낼 수 있고
끝까지 진행했는데도 찾지 못했다면, 없는 것이기 때문에 -1을 반환하게 된다
import java.util.Arrays;
public class BinarySearchSample {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11}; // 정렬된 배열
Arrays.sort(arr); // 배열이 정렬되지 않았을 경우 사용
int target = 5; // 찾고자 하는 값
int result = Arrays.binarySearch(arr, target);
// 있을 경우 배열 인덱스, 없을 경우 음수 반환
if (result < 0) {
System.out.println(target + "은(는) 배열에 없습니다.");
} else {
System.out.println(target + "은(는) 배열의 인덱스 " + result + "에 있습니다.");
}
}
}이후 이진 탐색이 어떻게 굴러가는지 이해했다면, 매번 구현하는 대신 Arrays.binarySearch(배열, 찾는_값); 을 사용하면 이진 탐색 방식으로 찾아오기 때문에 원리를 알고 있다면 매번 구현할 필요가 없다.
Leave a Reply