[Algorithm] 이진탐색(Binary Search) 알고리즘

이진탐색 (Binary Search)

 

이진탐색이란?

이분탐색으로도 불리며 말 그대로 일정한 구간, 범위 등을 2개로 나누어 탐색 범위를 좁혀나가는 탐색 과정
즉, 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘으로 탐색속도가 빠르다는 장점이 있다.

[그림] 이진탐색 원리

이진탐색 소스코드 구현 (Java)

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

    while (start <= end) {
        mid = (start + end) / 2;
        if (target == arr[mid]) {
            return mid;
        }else if (arr[mid] < target) {
            start = mid + 1;
        }else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target.");
}

예제) 이진탐색 예제 - 백준 12단계 10815번 숫자카드 중 (Java)

public static int binarySearch(int cards[], int n, int search){
    int first = 0;
    int last = n -1; //배열 마지막 인덱스
    int mid = 0;

    while(first <= last){
        mid = (first + last)/2;
        if(cards[mid] == search){
            return 1;
        }
        if(cards[mid] < search)
            first = mid + 1;
        else last = mid - 1;
    }
    return 0;
}