Typiler

바이너리 서치와 바이너리 서치 트리는 차이가 있습니다. 이중 오늘 공부할 내용은 바이너리 서치(Binary Search) 입니다. 자료구조가 아니라 알고리즘입니다. 바이너리 서치는 정렬되어있는 상태에서 내가 원하는 값을 찾고 싶을때 찾는 알고리즘 입니다. 여기서 정렬되어있는 상태가 중요합니다. 이것이 기본조건입니다. 데이터를 빨리 찾기 위한 방법입니다.

동작과정

1. 데이터를 정렬한다.
2. 범위를 반씩 좁혀가며 데이터를 찾는다.

시간복잡도

한번 탐색할때 마다 크기를 반으로 줄이기 때문에 시간복잡도는 O( log N ) 이 됩니다.

참고사이트

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

기본코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;


class 바이너리서치_기본코드 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] arr = {50,30,1,2,5,7,9,10};
    static int tar = 7;
    
    static void bSearch(int s, int e){
    	while(s<=e){
    		int mid = (s+e)/2;
    		int mVal = arr[mid];
    		
    		if(mVal == tar){
    			System.out.println("발견");
    			return;
    		}
    		
    		if(mVal < tar) s= mid + 1;
    		else e = mid - 1;
    	};
    	
    	System.out.println("미발견");
    }
    
    public static void main(String[] args) throws IOException {      
    	
    	// 바이너리 전제조건 => 정렬이 필수
    	Arrays.sort(arr);
    	
    	bSearch(0,arr.length-1);
    	
        br.close();
        bw.close();        
    }
}