[알고리즘] Binary Search and Recursive

Binary Search의 기본 전제는 데이터가 이미 정렬되어 있어야 한다는 점입니다. 시간 복잡도는 O(logN)이며 선형검색보다 빠르게 검색할 수 있다는 장점이 있습니다.

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class BinSearch {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("요소수: ");
		int num=sc.nextInt();
		int[] x=new int[num]; //요소수 사이즈가 num
		
		System.out.println("오름차순으로 입력하세요.");
		
		System.out.print("x[0]: ");
		x[0]=sc.nextInt();
		
		for(int i=1;i<num;i++) {
			do {
				System.out.print("x["+i+"]: ");
				x[i]=sc.nextInt();
				}while(x[i]<x[i-1]); //바로앞의 요소보다 작으면 다시입력
		}
		
		System.out.println("검색할 값: ");
		int ky=sc.nextInt();
		//int idx=binSearch(x,num,ky);
		int idx=Arrays.binarySearch(x, ky); //자바에서 제공해주는 바이너리서치 사용
		if(idx<0) {
			System.out.println("해당값 없음");
		}else {
			System.out.println("그 값은 x["+idx+"]에 있습니다");
		}
	}

	private static int binSearch(int[] x, int num, int ky) {// 내가 만든 binary Search
		// TODO Auto-generated method stub
		int first=0;
		int end=num-1;// 끝 값위치	
		//int middle=(first+end/2);//가운데 위치
		
		while(true){
			int middle=(first+end/2);
			if(x[middle]==ky) {
				return middle;
			}else if(x[middle]<ky) {
				first=middle+1;
				//middle=(first+end)/2;
			}else {
				end=middle-1;
				//middle=(first+end)/2;
				}
			if(first>end) {
				break;
			}
		}
		
		return -1;
	}

}

재귀란?

어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의 하고 있을 때를 재귀라고 합니다.

재귀 알고리즘은 코드가 간단해지며 종료할 조건이 반드시 필요합니다.

import java.util.Scanner;

public class Factorial {
	
	static int factorial(int n){
		if(n>0){
			return n*factorial(n-1);
		}else {
			return 1;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		System.out.println("팩토리얼할수 를 입력하시오");
		int num=sc.nextInt();
		System.out.println(num+"! = "+ factorial(num));
		int repeat=1;
		for(int i=num;i>0;i--) {
			repeat*=i;
		}
		System.out.println("반복문 사용: "+ repeat);		
	}
}

이진 검색을 재귀함수를 이용해서 만들어보자

public class BinSearch {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("요소수: ");
		int num=sc.nextInt();
		int[] x=new int[num]; //요소수 사이즈가 num
		
		System.out.println("오름차순으로 입력하세요.");
		
		System.out.print("x[0]: ");
		x[0]=sc.nextInt();
		
		for(int i=1;i<num;i++) {
			do {
				System.out.print("x["+i+"]: ");
				x[i]=sc.nextInt();
				}while(x[i]<x[i-1]); //바로앞의 요소보다 작으면 다시입력
		}
		
		System.out.println("검색할 값: ");
		int ky=sc.nextInt();
		int idx=binSearch(x,0,num,ky);
		//int idx=Arrays.binarySearch(x, ky);
		if(idx<0) {
			System.out.println("해당값 없음");
		}else {
			System.out.println("그 값은 x["+idx+"]에 있습니다");
		}
	}
	private static int binSearch(int[] x,int f,int size,int key) {
		int first=f;
		int end=0;
		if(size==x.length) {
			end=size-1;
		}else {
			end=size;
		}
		int middle=(first+end)/2;
		if(first>end) {
			return -1;
		}else {
			if(x[middle]==key) {
				return middle;
			}else if(x[middle]<key){
				first=middle+1;
				return binSearch(x,first,end,key);
			}else {
				end=middle-1;
				return binSearch(x,first,end,key);
			}
	
		}
	}
}