package Practice;
import java.util.Scanner;
public class BinarySearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("배열의 크기를 입력하세요.");
int size = sc.nextInt();
int[] arr = new int[size];
for (int i=0; i<arr.length; i++) {
System.out.println("arr[" + i + "]에 해당하는 숫자를 입력하세요");
arr[i] = sc.nextInt();
}
System.out.println("1. 순환 호출을 이용한 이진 검색");
System.out.println(binarySearch1(arr, 5, 0, arr.length-1)); // 2
System.out.println("\n2. 반복을 이용한 이진 검색");
System.out.println(binarySearch2(arr, 20, 0, arr.length-1)); // 6
sc.close();
}
static int binarySearch1(int[] arr, 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(arr, key ,low, mid-1); // 왼쪽 부분 탐색
} else {
return binarySearch1(arr, key, mid+1, high); // 오른쪽 부분 탐색
}
}
return -1; // 탐색 실패
}
static int binarySearch2(int[] arr, int key, int low, int high) {
int mid;
while(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) {
return mid;
} else if(key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // 탐색 실패
}
}