검색 알고리즘(이진탐색)

검색 알고리즘

1. 선형검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행
   - 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
   - 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

검색 외에도 데이터 삽입 및 삭제 작업에서 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야한다.
선택한 알고리즘의 용도나 목적, 실행속도, 자료구조 등을 고려하여 알고리즘을 선택

---

순차 탐색(sequential search)

• 검색 대상의 자료를 처음부터 하나씩 비교하여 검색한다.
• 검색 대상 자료가 순서적으로 정렬되어 있지 않아도 검색이 가능하다.
• 검색 대상 자료들의 수를 알지 못할 때 사용한다.
• 단순하고 검색 속도가 느림으로 자료가 적을 때 유리하다.
• 검색 대상이 배열에 없을 경우 최악의 경우로 n번 검색한다.
• 시간 복잡도
  • worst case : O(n) -> 검색에 실패한 경우
  • Average case : O((n+1)/2)

static int seqSearch(int[] a, int n, int key){
    for(int i=0;i<n;i++)
    if(a[i]==key) return i; //검색 성공
    return -1;              //검색 실패
}

---

이진 탐색(binary search)

• 검색 대상의 전체 자료를 이등분 하면서 검색하는 방법이다.
• 이진 탐색을 하려면 검색 대상의 전체 자료의 수를 알고 있어야 한다.
• 이진 탐색을 하려면 검색 대상의 자료들이 정렬 되어있어야 한다.
• 시간 복잡도
  • worst case : O(log n)+1 -> 검색에 실패한 경우
  • Average case : O(log n) -> 검색 범위를 반씩 좁혀나감

static int binarysearch(int[] a, int key){
    Arrays.sort(a); //이진 탐색은 정렬된 상태에서 시작
    int left = 0;
    int right = a.length()-1;   //최악의 경우

    while(left>=right){
        int mid = (left+right)/2;   //중간값 mid
        if(mid>key)left = mid+1;        //배열의 왼쪽 탐색
        else if(mid<key) right = mid-1; //배열의 오른쪽 탐색
        else return mid;    //mid == key
    }
    return -1;
}

java.util.Arrays 클래스에는 binarySearch 메서드가 있다.
binarySearch 메서드는 오름차순으로 정렬된 배열을 가정하고, 키 값이 key인 요소를 이진검색한다.

binarySearch 메서드는 자료형에 따라 9가지 방법으로 오버로딩 되어 있습니다.

검색에 성공한 경우 
    - 일치하는 요소의 인덱스를 반환
    - 일치하는 요소가 여러개 있다면 무작위로 인덱스를 반환

검색에 실패한 경우
    - 삽입 포인트를 x라고 할 때 -x-1을 반환(음수의 숫자를 반환)

static int BS(int[] x, int key){
    Arrays.sort(x);     //binarySearch 전에 배열 정렬
    int idx = Arrays.binarySearch(x,key);   //배열 x에서 키 값이 key인 요소를 검색  
}

---

이진 트리 검색(Binary Tree Search)

• 검색 대상의 자료를 이진 트리로 변형한 뒤 검색하는 방법
• 처음의 자료는 근노드가 되고, 두번째 자료는 근노드와 비교해서 작으면 왼쪽으로, 크면 오른쪽에 연결한다.
• 모두 연결된 이진 트리를 근 노드에 있는 값을 비교하여 찾고자 하는 값에 따라 왼쪽 또는 오른쪽을 다시 비교한다.
• 비어있지 않다면 모든 노드(node)는 서로 다른 값(key)을 갖습니다.
• 시간 복잡도
  • O(log n)

다음의 코드는 이진트리의 삽입과 삭제 검색을 구현한 알고리즘이다.

package algorithm.Search;

import java.util.Comparator;

public class BinTree <K,V>{
    //노드
    static class Node<K,V>{
        private K key;  //키 값
        private V data; //데이터
        private Node<K,V> left;     //왼쪽 자식 노드
        private Node<K,V> right;    //오른쪽 자식 노드

        //생성자
        Node(K key,V data, Node<K,V> left, Node<K,V> right){
            this.key = key;
            this.data = data;
            this.left = left;
            this.right = right;
        }
        K getKey(){ return key;}
        V getValue(){ return data;}
        void print(){ System.out.println(data);}
    }

    private Node<K,V> root;     //루트(첫번째 노드)
    private Comparator<? super K> comparator = null;    //비교자

    //노드가 하나도 없는 트리 생성
    public BinTree(){ root = null;} //자연 순서로 키 값을 비교

    //인수로 비교자를 전달받는 생성자
    public BinTree(Comparator<? super K> c){    //비교자로 키 비교
        this();     //this()에 의해 인수를 전달받지 않는 생성자 BinTree를 호출(root = null 인 이진검색 트리 생성)
        comparator = c;     //필드 comparator에 전달받은 c를 설정
    }

    //두 키 값을 비교하는 comp 메서드
    private int comp(K key1, K key2){
        return (comparator==null) ? ((Comparable<K>)key1).compareTo(key2) : comparator.compare(key1,key2);
        //key1>key2 =>양수
        //key1<key2 =>음수
        //key1==key2 => 0
    }

    //이진검색트리에서 노드를 검색
    public V search(K key){
        Node<K,V> p = root;

        while(true){
            if(p==null) return null;            //더이상 진행하지 않으면 검색 실패
            int cond = comp(key,p.getKey());    //key와 노드 p의 키를 비교
            if(cond==0) return p.getValue();    //같으면 검색 성공 => 노드의 데이터에 대한 참조를 반환
            else if(cond<0) p=p.left;           //key 쪽이 더 작으면 왼쪽 서브트리에서 검색
            else p=p.right;                     //key 쪽이 더 크면 오른쪽 서브트리에서 검색
        }
    }

    //node를 루트로 하는 서브트리에 노드<K,V>를 삽입
    private void addNode(Node<K,V> node, K key, V data){
        int cond = comp(key,node.getKey());
        if(cond==0)return;  //삽입 과정에서 key가 이미 이진 트리에 있음
        else if(cond<0){    //왼쪽 서브트리
            if(node.left==null) node.left = new Node<K,V>(key,data,null,null);  //서브트리가 비어있으면 노드 생성
            else addNode(node.left, key,data);      //왼쪽 노드 탐색
        }
        else{       //오른쪽 서브트리
            if(node.right==null) node.right = new Node<K,V>(key,data,null,null);
            else addNode(node.right,key,data);  //오른쪽 노드 탐색
        }
    }

    public void add(K key, V data){
        if(root==null) root = new Node(key,data,null,null); //트리가 비어있는 상태이므로 첫번째 루트 생성
        else addNode(root,key,data);    //addNode를 호출하여 노드를 삽입
    }

    //Node를 삭제하는 remove 메서드
    public boolean remove(K key){
        Node<K,V> p = root;
        Node<K,V> parent = null;
        boolean isLeftChild = true;
        //1. 자식 노드가 없는 노드를 삭제하는 경우
        while(true){
            if(p==null) return false;   //더이상 진행하지 않으면 키 값이 없음
            int cond = comp(key,p.getKey());
            if(cond==0) break;  //key와 노드 p의 키 값을 비교해서 같으면 검색 성공
            else{
                parent = p;         //가지로 내려가기 전에 부모를 설정
                if(cond<0){
                    isLeftChild = true;
                    p = p.left;     //왼쪽 서브트리에서 검색
                }
                else{
                    isLeftChild = false;    //key쪽이 크면 오른쪽 자식으로 내려감
                    p = p.right;    //오른쪽 서브트리에서 검색
                }
            }
        }
        //2. 자식 노드가 1개인 노드를 삭제하는 경우
        if(p.left==null){   //p에 왼쪽 자식이 없을 때
            if(p==root) root = p.right;
            else if(isLeftChild) parent.left = p.right;     //부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
            else parent.right = p.right;        //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
        }
        else if(p.right==null){     //p에 오른쪽 자식이 없을 때
            if(p==root) root = p.left;
            else if(isLeftChild) parent.left = p.left;      //부모의 왼쪽 포인터가 왼쪽 자식을 가리킴
            else parent.right = p.left;         //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
        }
        //3. 자식 노드가 2개인 노드를 삭제하는 경우
        else{
            parent = p;
            Node<K,V> left = p.left;    //서브 트리 가운데 가장 큰 노드
            isLeftChild = true;
            while(left.right!=null){    //가장 큰 노드 left를 검색
                parent = left;
                left = left.right;
                isLeftChild = false;
            }
            p.key = left.key;       //left의 key와 data를 p로 옮김
            p.data = left.data;
            if(isLeftChild) parent.left = left.left;    //left를 삭제
            else parent.right = left.left;  //left를 삭제
        }
        return true;
    }

    //모든 노드를 출력하는 print 메서드
    //inorder 방법으로 트리를 검색하는 방법
    private void printSubTree(Node node){
        if(node!=null){
            printSubTree(node.left);    //왼쪽 서브 트리를 키 값의 오름차순으로 출력
            System.out.println(node.key+" "+node.data);     //해당 node를 출력
            printSubTree(node.right);   //오른쪽 서브 트리를 키 값의 오름차순으로 출력
        }
    }
    //모든 노드를 키 값의 오름차순으로 출력
    public void print(){
        printSubTree(root);
    }

}