[알고리즘] Binary Search

1. Binary Search 란?

• 정렬된 배열에서 찾고자 하는 요소를 빨리 찾는 알고리즘 입니다.
• Binary Search Tree에서 자주 사용됩니다.

 

동작원리

• 배열의 중간 원소를 선택합니다.
• 이 원소가 찾고자 하는 값과 같다면 검색은 종료됩니다.
• 만약 중간 원소가 찾고자 하는 값보다 작다면, 배열의 오른쪽 반을 대상으로 이진 검색을 계속 진행합니다.
• 만약 중간 원소가 찾고자 하는 값보다 크다면, 배열의 왼쪽 반을 대상으로 이진 검색을 계속 진행합니다.
• 배열의 크기가 0이 될 때까지 원하는 값을 찾지 못하면, 해당 원소는 배열 내에 없는 것으로 판단합니다.

 

2. 구현

Array

public class BinarySearch {
	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;
    }
}

 

BinarySearchTree

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);        
    }
}