안녕하세요 오늘은 이진 탐색에 대해 알아보겠습니다. 이진 탐색이란 정렬된 데이터나 리스트에서 특정한 값을 빠르게 찾아내는 알고리즘입니다. 중간에 있는 임의의 값을 선택하여 찾고자 하는 값과 X와 비교합니다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간 값보다 크면 우측을 대상으로 다시 탐색합니다. 다시 중간 값을 임의로 선택하고 비교합니다. 해당 값을 찾을 때까지 반복합니다.
1. 이진 탐색의 예시
int[] arr = {1, 5, 11, 16, 23, 38, 54, 66, 87, 100};순차적으로 정렬된 배열이 있습니다. 이 배열에서 이진 탐색을 이용하여 38의 값을 찾아보겠습니다.
①첫 번째
- 가운데 위치한 23을 선택합니다.
- 선택한 값 23과 38을 비교합니다.
- 23보다 38이 크므로 38은 23의 우측에 있다는 것을 알 수 있습니다.
②두 번째
- 23을 기준으로 우측에 있는 배열 값들을 대상으로 다시 탐색합니다.
- 가운데 있는 66을 선택합니다.
- 66보다 38이 작으므로 66의 좌측에 있다는 것을 알 수 있습니다.
③세 번째
-가운데 위치한 수는 38이므로 38을 세 번째 만에 찾은 것을 알 수 있습니다.
2. 이진 탐색 코드 구현
Scanner로 사용자의 입력을 받아 원하는 숫자를 찾는 코드를 구현해 보겠습니다.
①main 함수
import java.util.Scanner;
public class BinarySearch {
static int[] arr = {1, 5, 11, 16, 23, 38, 54, 66, 87, 100};
public static void main(String[] args) {
System.out.println("======이진 탐색======");
Scanner sc = new Scanner(System.in);
System.out.print("숫자를 입력해주세요 : ");
int num = sc.nextInt();
System.out.println(binarySearch1(num, 0, arr.length-1)); //0부터 배열 길이-1 까지
}사용자가 숫자를 입력하면 이진 탐색 기법으로 숫자가 몇 번째 있는 지 찾습니다.
binartSearch 메소드 괄호에는 찾고 싶은 숫자, 배열의 처음, 배열 끝을 입력합니다.
②재귀적 탐색
// 재귀적 탐색
static int binarySearch1(int key, int low, int high) {
int mid;
if(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) { // 탐색 성공
return mid;
} else if(key < arr[mid]) {
return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색
} else {
return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색
}
}
return -1; // 탐색 실패 시 -1 반환
}
}재귀 함수를 이용하여 재귀적으로 탐색하는 코드입니다. 이진 탐색 예시에서 했던 방식을 코드로 구현했습니다.
3. 결과
38을 찾으면 배열의 인덱스 번호 0부터 시작해서 5번째인 위치에 있다고 성공적으로 구현했습니다.
