1. 개념

정렬된 리스트 형태로 주어진 원소에 대해 탐색 대상의 크기를 절반씩 줄여 가면서 탐색 키를 가진 원소를 찾는 방식

2. 과정

리스트는 일차원 배열에 저장된 것으로, 정렬은 오름차순 정렬로 가정

1. 배열의 가운데 원소와 탐색 키 key를 비교한다.
2. 두 값이 같은 경우 원하는 키를 찾았으므로 탐색을 종료하고, 두 값이 같지 않은 경우 배열을 가운데 원소를 기준으로 왼쪽과 오른쪽의 2개의 부분배열로 분할한다.
3. 탐색 키 key가 가운데 원소보다 작으면 왼쪽 부분배열(배열의 전반 부분)에 대해 이진 탐색을 다시 수행하고, key가 가운데 원소보다 크면 오른쪽 부분배열(배열의 후반 부분)에 대해 이진 탐색을 다시 수행한다.
4. 탐색 키 key를 찾을 때까지, 혹은 이진 탐색의 대상이 되는 부분배열이 빈 배열이 되어 탐색 키 key가 존재하지 않음을 알게 될 때까지 1~3의 과정을 반복한다.

3. 구현

public class BinarySearch {
	/**
     * 이진 검색 메서드
     */
	static int binarySearch(int[] array, int length, int key) {
    	int left = 0;	// 검색 범위의 첫 인덱스
        int right = length - 1;	// 검색 범위의 끝 인덱스
        
        do {
        	int center = (left + right) / 2;	// 중앙 요소의 인덱스
            if (array[center] == key) {	// 중앙 요소의 값과 key 값이 같은 경우
            	return center;	// 검색 성공
            } else if (array[center] < key) {	// 중앙 요소의 값보다 key 값이 큰(오른쪽에 있는) 경우
            	left = center + 1;	// 검색 범위를 뒤쪽 절반으로 축소
            } else {	// 중앙 요소의 값보다 key 값이 작은(왼쪽에 있는) 경우
            	right = center - 1;	// 검색 범위를 앞쪽 절반으로 축소
            }
        } while (left <= right);
        
        return -1;	// 검색 실패
    }
    
    public static void main(String[] args) {
    	int[] array = {15, 27, 39, 77, 92, 108, 121};
        
        int key = 39;	// 키 값
        
        int index = binarySearch(array, array.length, key);	// 배열 array에서 키 값이 key인 요소를 검색
        
        if (index == -1) {
        	System.out.println("값이 존재하지 않습니다.");
        } else {
        	System.out.println(key + "을(를) 찾았습니다!");
        }
    }
}

4. 성능 분석

static int binarySearch(int[] array, int length, int key) {
	int left = 0;	// O(1)
    int right = length - 1;	// O(1)
    
    do {
        int center = (left + right) / 2;	// O(log n)
        if (array[center] == key) {	// O(log n)
        	return center;	// O(n)
        } else if (array[center] < key) {	// O(log n)
        	left = center + 1;	// O(log n)
        } else {
        	right = center - 1;	// O(log n)
        }
    } while (left <= right);	// O(log n)
    
    return -1;	// O(1)
}

• 전체 시간 복잡도 : O(log n)

  O(1) + O(1) + O(log n) + O(log n) + O(1) + O(log n) + O(log n) + O(log n) + O(log n) + O(1) = O(log n)

5. 특징

✅ 정렬되고 크기가 작은 데이터에 적합하다.

• 입력이 정렬된 리스트에 대해서만 적용 가능

• 입력 데이터의 정렬 여부를 알 수 없을 경우 → 초기화 연산 이용

  • 초기화 연산 : O(nlogn)

    이진 탐색 수행의 대전제는 원소들이 정렬되어 있다는 것

    1. 주어진 원소들이 정렬되어 있는지 확인한다.
    2. 정렬되어 있지 않다면 오름차순으로 정렬한다.

  • 삽입 연산 : O(n)

    삽입이 끝났을 때 정렬 상태가 유지되어야 함

    1. 새로운 원소를 탐색 키로 하여 이진 탐색을 먼저 진행하여 추가될 위치를 찾는다.
    2. 오른쪽 원소들을 모두 오른쪽으로 한 칸씩 이동 후 해당 위치에 새로운 원소를 추가한다.

  • 삭제 연산 : O(n)

    삭제가 끝났을 때 정렬 상태가 유지되어야 함

    1. 이진 탐색으로 삭제할 원소를 찾아 이 원소를 삭제한다.
    2. 오른쪽 원소들을 모두 왼쪽으로 한 칸씩 이동한다.

---

📖 참고

• 이관용, 김진욱(2024). 알고리즘. 한국방송통신대학교출판문화원
• Bohyoh Shibata. (2020). Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바편(강민 옮김). 이지스퍼블리싱