[알고리즘] Seach: Binary Search

1. Binary Search 란?

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

 

과정

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

 

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