이진 탐색

순차적으로 정렬되어있을 때 검색하는 가장 기본적인 검색방식이다.

 

방법은 중간값을 원하는 검색 값과 비교해서 검색하는 방식인데, 작을 땐 범위 아래로 내려서 O(logN) 의 시간복잡도를

갖고있다. 모든 자료를 순차로 탐색하는 것보다 효율이 좋아 자주쓰일 듯 하다.

구현도 쉬운편이고, 효율도 어느정도는 나오기에 구현 방식을 잘 기억해둬야겠다.

간단한 그림 예제와 소스코드 예제를 통해 익혀두기.

그림 예제

이 방식의 핵심은 제일 낮은 인덱스, 제일 큰 인덱스, 중간값 이 세 값을 구하는게 중요한데 중간 값(A[Center])비교를 기준으로 설명하자면

Max : 검색 값이 낮을 때 - Center대입

          검색 값이 높을 때 - 그대로

Min : 검색 값이 낮을 때 - 그대로

         검색 값이 높을 때 - Center대입

Center : 항상 (Min + Max) / 2를 해주면 중간값을 정할 수 있다.

첫번째 구역 나누기

두번째 구역 나누기

 

세번째 구역 나누기

네번째 구역 나누기

마지막 A[0]의 값이 찾는 값과 같다면 "값을 찾았습니다!"

아니라면 "찾는 값이 없어요"가 출력된다.

 

 

소스코드 예제

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int[] a = {39, 41, 53, 55, 68, 72, 84, 88, 92, 97, 102};
        
        Scanner sc = new Scanner(System.in);
        
        int b = sc.nextInt();
        int center = 0;
        
        int max = a.length;
        int min = 0;
        
        center = a.length/2;
        
        while(true) {
            if(b == a[center]) {
                System.out.println("값을 찾았습니다!");
                break;
            }
            else if(center == 0) {
                System.out.println("찾는 값이 없어요");
                break;
            }
            else if(b < a[center]) {
                //min 안건드림
                max = center;
                center = (min + max) / 2;
                
                System.out.println("b가 작아 min : " + min + "| max : " + max + "| center : " + center);
            }
            else if(b > a[center]) {
                min = center;
                //max 안건드림
                center = (min + max) / 2;
                
                System.out.println("b가 커 min : " + min + "| max : " + max + "| center : " + center);
            }
        }
    }
}
 

-------------

위에 있는 소스는 23.01.14 다른 문제를 풀다 알게된건데 틀린 예제입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String[] args) throws NumberFormatException, IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] a = new long[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        int left;
        int right;
        int center;
        
        long key = 0;
        int isTrue = 0;
        
        for(int i = 0; i < m; i++) {
            key = Integer.parseInt(st.nextToken());
            left = 0;
            right = a.length - 1;
            center = right / 2;
            isTrue = 0;
            while(left <= right) {
                if(a[center] == key) {
                    System.out.println("1");
                    isTrue = 1;
                    break;
                }
                else if(a[center] > key) {
                    right = center - 1;
                    center = (left + right) / 2;
                }
                else if(a[center] <key) {
                    left = center + 1;
                    center = (left + right) / 2;
                }
                
            }
            if(isTrue == 0) {
                System.out.println("0");
            }
        }
    }
}

일단 간단한 예제를 올리기 전에 고쳐놓기....

요건 제 기준 어려운 예제임당...