[알고리즘] 이진 탐색

1. 개념

정렬되어 있는 데이터에서 원하는 값을 찾을 수 있는 알고리즘. 정렬되어 있는 데이터 중 중앙값을 찾고, 그 중앙값과 내가 찾고자 하는 값을 비교해서 찾고자 하는 값이 더 작으면 중앙에서 왼쪽만 보고, 찾고자 하는 값이 더 크면 중앙에서 오른쪽만 본다. 이렇게 하면 살펴야 하는 데이터의 크기를 절반씩 줄여나갈 수 있다.

 

2. 예시

데이터: 3 7 13 15 23 35 38 40

찾고자 하는 데이터: 13

• 맨 처음 중앙값은 15, 찾고자 하는 값이 더 작으니 15보다 왼쪽만 본다.
• 15보다 왼쪽 중 중앙값은 7, 찾고자 하는 값이 더 크니 7보다 오른쪽만 본다.
• 7보다 오른쪽 중 중앙값은 13. 찾고자 하는 값을 찾았다.

 

3. 특징

• N개의 데이터에서 logN번의 연산으로 원하는 데이터를 찾을 수 있다.
• 정렬이 되어 있어야만 적용이 가능하다.

 

4. 코드

// 반복문으로 구현

public static int BSearch(int[] arr, int target){
    int start = 0;
    int mid;
    int end = arr.length-1;

    while(start <= end){
        mid = (start + end) / 2;
        if(target < arr[mid]){
            end = mid-1;
        }else if(target > arr[mid]){
            start = mid + 1;
        }else{
            return arr[mid];
        }
    }
    return -1;
}

// 재귀로 구현

public static int BSearch(int[] arr, int target, int start, int end){
    if(start > end){
        return -1;
    }
    int mid = (start + end) / 2;
    if(target < arr[mid]){
        return BSearch(arr, target, start, mid-1);
    }else if(target > arr[mid]){
        return BSearch(arr, target, mid+1, end);
    }else{
        return arr[mid];
    }

}

 

5. 관련 문제

백준 1920

GitHub - Lee-Min-Jung/coding_test_practice

백준 2343

백준 1300

GitHub - Lee-Min-Jung/coding_test_practice