검색 알고리즘 종류

안녕하세요 열코입니다.

이번시간에는 기본적인 검색(탐색) 알고리즘 종류들에 대해 알아보도록 하겠습니다.

1. 선형 검색 (Linear Search)

- 배열의 가장 좌측부터 시작하여 찾으려는 값과 하나씩 배열의 각 요소와 비교합니다.

- 찾으려는 값을 발견한다면 배열의 해당 인덱스를 반환(return)합니다.

- 찾으려는 값이 없다면 -1을 반환합니다.

- 시간복잡도 O(n)

- 이진 검색 및 해시 테이블과 같은 다른 검색 알고리즘이 훨씬 빠르기 때문에 실제로 거의 사용하지 않습니다.

- 소스코드

int search(int arr[], int n, int x) { // 매개변수 : 배열이름, 배열의 길이, 찾으려는 값
 
    int i;
 
    for (i = 0; i < n; i++) { // 배열 전체 순차 탐색
 
        if (arr[i] == x) { // 찾는 값 발견
 
            return i; // 해당 위치(인덱스) 반환
 
        }
 
    }
 
    return -1; // 찾으려는 값을 발견하지 못하면 -1 반환
 
}

2. 이진 검색 (Binary Search)

- 검색 반경을 반으로 나눠어 반복하는 검색 방법입니다.

- 정렬 된 배열에서 사용 가능합니다.

- 찾으려는 값을 배열의 중간값과 비교하여 그 값이 더 작다면 우측 배열, 크다면 좌측 배열로 이동하여 반복

- 시간 복잡도 O(log n)

- 소스코드

int binarySearch(int arr[], int l, int r, int x) { // 매개변수 : 배열이름, 배열 시작 인덱스, 배열 끝 인덱스, 찾으려는 값
 
   if (r >= l) 
 
   { 
 
        int mid = l + (r - l)/2; // 중간 값 선택
 
        if (arr[mid] == x) // 비교하여 찾는 값이라면
 
            return mid; // 해당 인덱스 반환
 
 
        if (arr[mid] > x) // 찾으려는 값보다 크다면
 
            return binarySearch(arr, l, mid-1, x); // 좌측 배열 탐색
 
 
        return binarySearch(arr, mid+1, r, x); // 우측 배열 탐색
 
   }
 
   return -1;  // 찾으려는 값이 없다면 -1 반환
 
} 

- C++ STL에서는 이진 검색을 라이브러리로 제공합니다.

- binary_search(시작위치, 끝위치, 찾으려는값) 식으로 사용합니다.

- lower_bound는 찾으려는 값이 여러개 존재할 때 사용합니다. (upper_bound는 큰 인덱스를 반환)

- 배열(또는 리스트) 안에 찾으려는 값이 1개(단일) 존재한다면 해당 값의 인덱스를 반환합니다.

- 배열 안에 찾으려는 값이 2개 이상 존재한다면 해당 값 중 가장 앞쪽(낮은) 인덱스(num of first position)를 반환합니다.

- 배열 안에 찾으려는 값이 없을 경우 찾으려는 값 다음 위치의 인덱스를 반환합니다.

- 자바에서 Array.binarySearch() 또는 Collections.binarySearch()을 라이브러리로 사용할 수 있습니다.

- 만약 자바에서 이진 탐색을 사용하려면 전에 Array.sort() 메소드를 호출하여 배열을 정렬할 필요가 있습니다.

※ 배열 또는 리스트에서 최소값, 최대값 검색

- 정렬된 배열 또는 리스트에서는 양쪽 끝 값이 최소값 또는 최대값입니다.

- Divide and Conquer를 사용하여 O(log n) 시간에서 최소값 또는 최대값을 구할 수 있습니다.

- 소스코드

int findPeakUtil(int arr[], int low, int high, int n) 
 
{ 
 
    int mid = low + (high - low)/2; 
 
 
    if ((mid == 0 || arr[mid-1] <= arr[mid]) && 
 
            (mid == n-1 || arr[mid+1] <= arr[mid])) 
 
        return mid; 
 
 
    else if (mid > 0 && arr[mid-1] > arr[mid]) 
 
        return findPeakUtil(arr, low, (mid -1), n); 
 
 
 
    else return findPeakUtil(arr, (mid + 1), high, n); 
 
} 
 
 
int findPeak(int arr[], int n) 
 
{ 
 
    return findPeakUtil(arr, 0, n-1, n); 
 
} 

이상 ''에 대해 알아보았습니다.

질문 또는 오타나 잘못된 정보가 있는 경우 댓글로 달아주세요!

메인 페이지로 이동하시면 더 많은 자료를 볼 수 있습니다.

[관련 게시글]

2018/10/19 - [기타] - 프로그래밍 언어별 정리

2018/09/12 - [자료구조, 알고리즘] - 정렬 알고리즘 종류

2018/09/05 - [자료구조, 알고리즘] - 자료구조 힙(Heap)

2018/08/30 - [자료구조, 알고리즘] - 자료구조 트리(Tree)

2018/09/06 - [자료구조, 알고리즘] - 자료구조 그래프(Graph)

2018/09/05 - [자료구조, 알고리즘] - 자료구조 힙(Heap)

2018/09/01 - [자료구조, 알고리즘] - 자료구조 이진 탐색 트리(Binary Search Tree)

2018/08/19 - [자료구조, 알고리즘] - [자료구조] 큐 QUEUE

2018/08/19 - [자료구조, 알고리즘] - [자료구조] 스택 STACK

2018/10/12 - [기타] - 개발자 Q&A 커뮤니티 추천 - 세모지(세상의 모든 지식)