[Java] 자바 이분 검색 구현 / java 이분법/이분검색 쉽게 구현

2020-10-08

---

 

수학에서 이분법(二分法, Bisection method)은

근이 반드시 존재하는 폐구간을 이분한 후,

이 중 근이 존재하는 하위 폐구간을 선택하는 것을 반복하여서

근을 찾는 알고리즘이다.

 

간단하고 견고하며 해의 대략적 위치를 안다면

일정 오차 내에 있는 1개의 해는 무조건 도출이 가능하나,

상대적으로 느린 방식이다.

이분법은 근이 존재한다는 것 자체를 전제로 구간을 설정하는 것이므로

근이 존재할 가능성은 100%이므로 방정식이 간단하고

근 자체가 가장 중요한 목적인 경우 가장 적합한 방법이다.

---

이분법 그래프

 

출처 : 위키피디아

 

위의 정의를 보면 어렵게 느껴질 수 있지만 사실은 간단하다.

 

각 배열의 크기에서 처음위치과 끝위치을 더한 후 2로 나눈 중간값이

찾고자 하는 값보다 크면 전체 범위를 처음위치 + (중간위치 - 1)를 해주고

찾고자 하는 값보다 작으면 전체 범위를 (중간위치 + 1) + 끝위치를 해주면서

지속적으로 범위를 좁혀 원하는 값을 찾아가는 방식이다.

 

코드를 보면 좀 더 쉽게 이해할 수 있다.

---

 

import java.util.Scanner;

public class TemplateA {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int size = scan.nextInt();
		//배열의 크기를 입력
		int [] arr = new int [size];
		//size크기의 배열 생성
		
		for(int i = 0; i < size; i++) {
			arr[i] = scan.nextInt();
			//배열값 입력해준다.
		}
		
		int searchNum = scan.nextInt();
		//찾고자 하는 값 입력
		
		int start = 0;
		int end = size - 1;
		//배열의 시작위치 끝위치 변수
		
		int mid = 0;
		//중간값 저장 변수
		
		 while(true) {
			 if(start <= searchNum) {
				 mid = (start + end) / 2;
				 //중간값 구해줌
				 if(searchNum == arr[mid]) {
					 System.out.println("배열의 위치는: " + mid + " 찾는 값은: " + searchNum);
					 break;
					 //찾는 값과 해당 배열의 중간mid위치에 있는 값과 같으면 출력후 반복문 종료
				 }
				 
				 if(searchNum < arr[mid]) {
					 end = mid - 1;
					 //찾고자 하는 값이 중간값보다 작으면
					 //끝위치를 중간값에서 하나 뺀 값으로 재설정
				 }else {
					 start = mid + 1;
					//찾고자 하는 값이 중간값보다 크면
					//시작위치를 중간값에서 하나 더한 값으로 재설정
				 }
				 
			 }else {
				 System.out.println("찾고자 하는 값이 배열에 존재하지 않음");
				 //start > searchNum보다 커진 경우 출력
				 break;
			 }
		 }
		

	}

}