[Algorithm] 이진 검색 알고리즘

 

 

 

이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

 

 

 

 

 

예시를 보자!!

 

 

 

 

 

이렇게 가운데에 있는 값을 확인하면서 검색하는 방법이 이진검색이다.

 

 

처음 시작할 때 a = 0이고 b = n-1값이면 검색할 가운데 값은  (a+b) / 2 값이 된다.

 

 

오름차순일 때 키값이 찾으려는 값보다 크면 b값은 중앙값 - 1 이 되고

                   키값이 찾으려는 값보다 작으면 a값은 중앙값 + 1이 된다.

 

 

 

 

 

 

 

이 방법을 코드로 짜보면

 

import java.util.Scanner;

public class binarysearch {		

	static int binSearch(int[] x, int n, int key) {
    
		int a = 0;
		int b = n - 1;			
		
		do {
			int c = (a+b) / 2;   // c는 가운데 수
			if(x[c] == key)     // 찾았음 c 리턴
				return c;
			
			else if( x[c] < key)   // 찾으려는게 가운데보다 크면
				a = c + 1;
			
			else {             // 찾으려는게 가운데보다 작으면
				b = c - 1;
			} 
		}while (a <= b);
		
		return -1;   // 값을 찾지 못함
		
	}
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		System.out.print("요솟수 : ");
		int num = scan.nextInt();
		int[] x = new int[num];
		
		System.out.println("오름차순으로 입력!!!");
		
		System.out.print("x[0] : ");
		x[0] = scan.nextInt();
		
		for(int i = 1; i< num; i++) {
			do {
				System.out.print("x[" + i + "] : ");
				x[i] = scan.nextInt();
				
			}while(x[i] < x[i-1]);
		}
		
		System.out.print("검색할 값 : ");
		int key = scan.nextInt();
		
		int index = binSearch(x, num, key);
		
		if(index == -1)
			System.out.println("그 값의 요소가 존재하지 않습니다.");
		else {
			System.out.println(key + "은(는) x[" + index + "]에 있습니다.");
		}
	}
}

 

 

 

 

 

 

다음과 같다.