이진 탐색(Binary Search)

어쩌면 이글을 정렬을 공부하다 들어왔을것이다. 그러길 바라며 글을 작성한다..물론 내 공부가 크지만...

 

이진 탐색은 데이터가 이미 정렬된 상태에서 특정한 값을 찾고자 할때 사용한다.

원하는 값을 찾는 과정에서 앞에서 구하지 않고 배열의 중간값과 비교해 배열을 반으로 자르고

비교값이 가까운 배열에서 또 반으로 자르고 거기서 또 원하는값과 가까운 배열을 찾고 이것을 반복한다.

 

말이 어렵다면 바로 보여주겠다.

10 20 30 40 50 60 70 80 90 100

이런식의 배열이 있다. 우린 여기서 90을 찾아 보도록 하겠다.

1. 배열을 중간으로 나누고 90에 가까운 배열을 찾는다 = 60 70 80 90 100
2. 그럼 거기서 한번 더 나누고 90에 가까운 배열 = 80 90 100
3. 또 반으로 나눴더니 90이 나왔다.

정말 단순하게 설명했지만 이게 이진 탐색 즉, Binary Search이다.

이것을 코드로 나타내볼까?

static int binarySearch(int[] arr, int key) {
    int low =0;
    int high = arr.length - 1;
    int mid;
    
    while(low <= high) {
        mid = (low + high) / 2;
        
        if(target == arr[mid]) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
    }
    return -1;
}

내가 말하고 싶은 Binary Search의 코드이다. 

target을 찾기위해 반으로 자르고 또 자르고 를 반복한다.

그렇게 결국 원하는 값을 찾는과정인것이다.

 

시간복잡도를 계산해보자

target을 찾기위해 배열을 target/2를 반복한다.

그럼 전체를 N이라고 봤을때 나누어진 배열은 N/2, N/4, N/8 이런식으로 진행된다.

그럼 N/2의 count제곱이다. 

그럼 식은 자연스럽게 N = 2count제곱이 될테고

log2N = count 가 되고 상수는 제거하면서

logN = count이므로 즉, Binary Search의 시간복잡도는 logN이 되는것이다.

 

나중에 꼭 나타나게 될테니 그리고 꼭 알아둬야하니 기억해두자