동빈북 7장 내용정리 이진탐색(Binary Search)

이진탐색은 영어로는 Binary Search이다.

일반적으로 탐색할 때는

순서대로 탐색하는 순차 탐색 말그대로 순서대로 탐색하는 것이다.

그러나 이 방식은 찾는 데이터가 자료구조의 가장 끝부분에 들어가 있다면 이상황이 최악의 탐색상황이므로 O(N)의 시간 복잡도를 나타낸다.

이제 이거를 어떻게 효율적으로 탐색할 수 있는지에 대한 아이디어에서 나온것이 바로 이분탐색(이진탐색,Binary Search)이다.

만약 배열의 요소가

int[] list = {1,5,7,10,11,14,17,20,64,100};

라고 가정해보자.

만약에 찾고자 하는 key값이 100이라면 순차탐색을 하게되면 접근하는 요소의 순서가

1,5,7,10,11,14,17,20,64,100 순서로

총 10번을 방문하게 된다.(key값이 없더라도 마찬가지이다.)

하지만, 이진탐색의 로직은 반반 나누며 접근하게 된다.

(원래대로라면 그림을 그려서 설명해야겠지만 귀찮으니 생략..)

초기값으론 배열의 중앙값을 잡는다.

만약 그 중앙값이 찾고자 하는 값보다 크다면 right를 하나 줄이고 중앙값을 다시 초기화한다.

만약 그 중앙값이 찾고자 하는 값보다 작다면 left를 하나 증가시키고 중앙값을 다시 초기화한다.

만약 그 중앙값이 같다면 그 인덱스를 출력하고 끝낸다.

만약 left가 right보다 커지면 값은 없는것이다.

위와 같은 노테이션으로 작업이 진행된다. 처음에 준 배열의 요소를 가지고 100을 찾는다면

5 7 8 9 key is :10

와 같은 순서로 방문하게 된다.

탐색의 범위를 반씩 줄여가며 탐색하기 때문에 시간복잡도는 O(logN)이라고 할 수 있다.

단, 배열이 반드시 정렬되어 있어야만 이진탐색이 가능하다는 것은 어떻게 동작방식만 봐도 알 수 있을것이다. JAVA로 구현한 코드는 다음과 같다.

public class Main {
    static int[] totalPrice;
    public static void main(String[] args) throws IOException {
        int[] list = {1, 5, 7, 10, 11, 14, 17, 20, 64, 100};
        int key = 100;
        int left = 0;
        int right = list.length-1;
        int mid = list.length / 2;
        while (left<=right) {
            System.out.println(mid);
            if (list[mid] == key) {
                System.out.print("key is :"+ (mid+1));
                return;
            } else if (list[mid] < key) {
                left=mid+1;
            } else {
                right=mid-1;
            }
            mid=(left+right)/2;
        }
        System.out.println("없어 임마");
    }
}

다만, 이게 문제에 적용되면 굉장히 까다로운 문제가 된다.

단순히 탐색을 구현하는 것은 쉬운일이나 이것을 문제에 적용시키는 것 또는 적용시켜야 된다고 느끼기 까지는 많은 문제를 풀어봐야 가능한 일인 것 같다.