[20210928] 이진(이분) 검색 알고리즘

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; // 탐색 실패 
	}
}