[알고리즘] Seach: Binary Search

1. Binary Search 란?

• 정렬된 자료구조에서 원하는 값을 효율적으로 찾는 알고리즘 입니다.
• ✅ 탐색 구간을 절반씩 줄여가며 목표 값을 찾음
• ✅ 주로 Binary Search Tree에서 사용됩니다.

 

과정

1. 중간 원소 선택
2. 범위 지정
   • 찾고자 하는 값보다 작다면, 배열의 오른쪽 반을 대상으로 이진 검색
   • 찾고자 하는 값보다 크다면, 배열의 왼쪽 반을 대상으로 이진 검색
3. 찾을때까지 반복 (재귀적)

 

Lower Bound

• 찾고자 하는 값 이상의 원소들 중, 가장 작은 인덱스 값
• ✅ 내부적으로 루프에서 불변식을 유지하면서 범위를 좁혀감
• ➡️ 항상 반개구간을 유지함 [left, right)
• ➡️ left: 거짓인 마지막 구간을 바로 넘어선 위치
• ➡️ right: 항상 참인 최소 위치
• ✅ 배열이 정렬되어 있으므로 판정 함수는 단조적
• ➡️ 참 구간과 거짓 구간이 딱 한번만 갈라지고 다시 섞이지 않음
• ➡️ 경계까지 반복하게 됨 (left == right)

 

코드

int left = 0, right = n;

while (left < right) {
    long mid = (left+right)/2;

    if (arr[mid] >= n) right = mid;
    else left = mid+1;
}

return right;

 

Upper Bound

• 찾고자 하는 값보다 큰 원소들 중, 가장 작은 인덱스 값
• ✅ 내부적으로 루프에서 불변식을 유지하면서 범위를 좁혀감
• ✅ 항상 반개구간을 유지함 [left, right)

 

코드

int left = 0, right = n;

while (left < right) {
    long mid = (left+right)/2;

    if (arr[mid] > n) right = mid;
    else left = mid+1;
}

return right;

 

2. 구현

Array

public int search(int[] arr, int data) {
    int l = 0, r = arr.length-1;

    while (l <= r) {
        int m = (l+r)/2;

        if (arr[m] == data) return data;
        else if (arr[m] > data) r = m-1;
        else l = m+1;
    }

    return -1;
}

 

Binary Search Tree

public class BinarySearchTree {
    public int search(int data) {
    	return search(this.root, data);
    }
	 
    public Node search(Node node, int data) {
        if (node == null) return null;
        
    	if (node.data == data) return node;
        else if (node.data > data) return search(node.left, data);

        return search(node.right, data);        
    }
}