이진 탐색(Binary Search)

 

 

 

알고리즘을 풀다가 이진 탐색의 존재를 새까맣게 잊고 있었다는 것에 충격을 받아서 작성한다.

 

이진 탐색은 최악의 조건에서도 O(logN)의 시간 복잡도를 보장하는 획기적인 탐색 방법이다.

 

데이터들의 값을 반으로 나누어 가며 탐색을 진행하기 때문에 최소

의 시간 복잡도를 보장하는 것이다.

 

 

단, 탐색을 원하는 데이터들이 정렬이 되어 있어야 한다는 조건에서만 이진 탐색을 사용할 수 있다.

 

 

import java.util.ArrayList;

public class Test{
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=1; i<=100; i++){
            list.add(i);
        }

        System.out.println(bruteForce(list,76));
        System.out.println(binarySerch(list,76));
    }

    private static int binarySerch(ArrayList<Integer> list, int num) {

        int count = 0;
        int start = 0;
        int end = list.size()-1;

        while(start<=end){
            count++;
            int mid = (start+end)/2;
            int midNum = list.get(mid);
            if(midNum == num)    return count;
            else if(midNum > num)   end = mid - 1;
            else    start = mid + 1;
        }
        return -1;
    }

    private static int bruteForce(ArrayList<Integer> list, int num) {
        int count = 0;

        for(int n : list){
            count++;
            if(n == num)    return count;
        }
        return -1;
    }
}


/* 
실행 결과
76
6
*/

 

완전 탐색과 이진 탐색의 차이는 N이 커질수록 기하급수적으로 커질 것이다. 

 

완전 탐색으로는 시간 복잡도를 만족하기 어렵고, 데이터들이 정렬이 되어 있는 경우에는 이진 탐색을 고려해보자!!

 

 

이걸 왜 망각하고 있었을까.. 정말 의문이구만.ㅎ