2분 검색(분치 알고리즘)

분할 처리 알고리즘:
하나의 큰 문제를 상대적으로 작은 두 문제로 분해하여 각각 작은 문제를 해결하고 두 개의 작은 문제에 대한 처리 방식도 같다. 두 개의 작은 문제로 분해하여 그것들을 해결한다.
이 과정은 풀기 쉬운 기본값에 도달할 때까지 계속되었으니, 계속 분해할 필요가 없다
이분 검색은 분치 알고리즘의 실례이다
순환 2분 찾기

public class BinarySearch {
	private int[] data;
	
	public BinarySearch(int[] data){
		this.data = data;
	}
	
	public int search(int target){
		int min = 0;
		int max = data.length - 1;
		int n = 0;
		while(true){
			n = (min + max)/2;
			if(target > data[n])
				min = n + 1;
			if(target < data[n])
				max = n - 1;
			if(target == data[n])
				return n;
			if(max < min)
				return -1;
		}
	}
	
	public static void main(String[] args) {
		int[] ints = {1,2,7,9,25,44,66,99};
		BinarySearch bs = new BinarySearch(ints);
		System.out.println(bs.search(50));
		System.out.println(bs.search(44));
	}
}

-1
5

귀속 2분 찾기

public class BinarySearch {
	private int[] data;
	
	public BinarySearch(int[] data){
		this.data = data;
	}
	
	public int search(int target,int min,int max){
		if(min > max)
			return -1;
		int n = (min + max)/2;
		if(target > data[n])
			min = n + 1;
		if(target < data[n])
			max = n -1;
		if(target == data[n])
			return n;
		else
			return search(target,min,max);
	}
	
	public static void main(String[] args) {
		int[] ints = {1,2,7,9,25,44,66,99};
		BinarySearch bs = new BinarySearch(ints);
		System.out.println(bs.search(50,0,ints.length-1));
		System.out.println(bs.search(44,0,ints.length-1));
	}
}

-1
5