[Algorithm] 이진탐색(Binary Search)

이진탐색(Binary Search)

이진 탐색은 정렬된 상태에서 원하는 값이 어디에 있는지 찾는 탐색 방법 중 하나입니다.

우선 탐색 되지 않은 영역의 중간 값과 원하는 값이 일치하는지 체크하고, 2가지 경우에 따라 분기처리합니다. 우선...

1. 중간 값이 찾고자 하는 값보다 작은 경우 

중간 값이 시작 기준이 되고 배열의 끝 값이 끝 기준이 되어 중간 값을 다시 도출합니다.

2. 중간 값이 찾고자 하는 값보다 큰 경우

중간 값이 끝 기준이 되고 배열의 시작 값이 시작 기준이 되어 중간 값을 다시 도출합니다.

위 2가지 경우에 분기 처리가 완료되면, 다시 찾고자 하는 값과 비교를 합니다. 

찾고자 하는 값이 계속 도출되는 중간 값과 일치하는 경우 해당 탐색 루프를 벗어납니다. ㅎㅎ 

package Search;

import java.util.Scanner;

public class BinarySearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int []array = new int[n];
		for(int i=0; i<n; i++){
			array[i] = sc.nextInt();
		}
		
		int value = sc.nextInt();
		
		System.out.println(binarySearch(array, value)+1+" 번째 있음");

	}

	private static int binarySearch(int[] array, int value) {
		int mid = array.length/2;
		
		while(true){
		//	System.out.println(mid);
			if(array[mid] == value){
				return mid;
			}else{
				if(array[mid] < value){
					mid = (mid + array.length)/2;
				}else{
					mid = mid/2;
				}
			}
			
		}
	
	}

}