알고리즘 알고가자(3)

Linear Search(선형검색)

요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 찾을 때 까지 맨 앞부터 순서대로 요소를 검색하는 것을 선형검색, 또는 순차검색(Sequential Search) 라고 한다.

선형검색의 종료조건은
1. 검색할 값을 발견하지 못하고 배열의 끝을 지나는 경우
2. 검색할 값과 같은 요소를 발견할 경우
이다.

다음은 JAVA 코드로 선형검색을 구현해 보자

int seqSearch(int [] arr, int key){
        for(int i = 0 ; i < arr.length; i++){
            if(arr[i] == key)
                return i;
        }
        return -1; // 검색값이 배열에 없을경우 -1 반환
    }

Binary Search(이진검색)

만약 선형검색 알고리즘을 사용한다면, 검색 값을 찾기위해 모든 데이터를 일일이 비교해봐야 하기 때문에, 매우 비효율적인 방식으로 값을 찾게 된다.
선형검색의 시간복잡도는 최악의 경우 검색 값이 배열에 마지막에 있거나, 검색 값이 배열에 존재하지 않을 경우 모든 데이터를 검색해야 함으로,
O(n) 시간복잡도를 가지게 된다.

이와같은 비효율적인 검색 알고리즘을 만약, 요소(element)들이 정렬된 배열이 있다면, Binary Search 를 통해 보다 훨씬 효율적으로 검색할 수 있게된다.
Binary Search 는 쉽게 설명하면 (오름차순으로 정렬 된)배열의 중간 요소와 검색하려는 값과 비교해, 만약 중가 요소값이 검색값 보다 크다면 중간 이후 모든 요소의 값들은 검색하려는 값보다 큰 값이므로 검색에 제외시키는 방식이다 (반대로 중간 요소가 검색하려는 값보다 작다면, 중간 이전의 모든 값을 검색에서 제외)
따라서 이진 검색을 활용하면 O(log n) 시간복잡도를 가지게 된다.

다음으로 JAVA 코드로 이진검색을 구현해 보자

int binSearch2(int[] a, int key){
        int pl = 0;		// 검색하려는 배열의 첫번째 인덱스 
        int pr = a.length-1;	// 검색하려는 배열의 마지막 인덱스
        do{
            int pc = (pl+pr)/2; // 중앙값
            if(a[pc] == key){
                return pc;
            } else if( a[pc] < key) {
                pl = pc+1;
            } else
                pr = pc-1;
        } while (pl <= pr);
        return -1;
    }