이분 탐색 (Binary Search) ✌

순차 탐색은 프로그램이 간단하고 작은 배열의 탐색에 효과적일 수 있으나, 큰 배열에는 적합하지 않다.

정렬된 배열에서 가장 적합한 이분 탐색에 대해 알아보자. 👩‍🔬

이분 탐색은 배열의 중앙값을 조사해 찾고자 하는 데이터가 왼쪽부분에 있을지, 오른쪽 부분에 있을지 알아내 탐색의 범위를 반으로 줄인다.

위 그림을 두 가지 방법으로 코드화 할 수 있다.

1. 재귀를 이용한 이분 탐색

int binarySearch(int key, int[] list, int first, int last) {
    int middle;
    
    if (first <= last) {
        middle = (first + last) / 2;
        if (key == list[middle]) {
            return middle;
        }
        else if (ket < list[middle]) {
            return binarySearch(key, list, first, middle - 1);
        }
        else {
            return binarySearch(key, lisy, middle + 1, last);
        }
    }
    return -1; // 탐색 실패
}

2. 반복을 이용한 이분 탐색

int binarySearch(int key, int[] list, int first, int last) {
	int middle;
    
    while (first <= last) {
        middle = (first + last) / 2;
        if (key == list[middle]) {
            return middle;
        }
        else if (key > list[middle]) {
            first = middle + 1;
        }
        else {
            last = middle - 1;
        }
    }
    return -1; // 탐색 실패
}

BOJ 관련 문제

-> 코드

-> 풀이