18 일차

선형 탐색과 이진 탐색

∙ 선형 탐색 (linear search)

- 전체 자료를 처음부터 마지막까지 순서대로 탐색하는 방법. -> 순차 탐색

- 시간 복잡도 : O(n)

- 선형 탐색의 장단점

> 장점 : 가장 간단하고 직관적인 방법이며, 정렬되지 않은 데이터에도 적용 가능

> 단점 : 비효율적(최악의 경우 배열 전체를 탐색해야 함)

bool liner_search(int data[], int n, int target)
{
	for (int i = 0; i < n; i++){
    	if (data[i] == target)
        	return true;
    }
    return false;
}

 

 

∙ 이진 탐색

- 정렬된 배열에 대해 검색 단계별로 검색 범위를 반으로 줄여가면서 데이터를 탐색하는 기법

- 시간 복잡도 : O(log n)

- 이진 탐색의 장단점

> 장점 : 검색 속도가 빠름

> 단점 : 이미 정렬되어 있는 데이터에만 적용 가능 

// 배열의 이름, 배열의 크기, 찾고자 하는 정수
bool binary_search(int data[], int n, int target)
{
	int lower = 0;
    int upper = n - 1;
    
    while (lower <= upper){
    	int mid = (lower + upper) / 2;
        
        if (data[mid] == target)
        	return true;
        else if (data[mid] < target)
        	lower = mid + 1;
        else
        	upper = mid - 1;
    }
    return false;
}

 

∙ std::binary_search() 함수

- 정렬된 컨테이너에서 (first, last) 범위 안에 value값이 있는지를 검사

- 최소 (first, last) 범위 안에서라도 정렬이 되어 있어야 동작

- 기본적으로 < 연산자를 이용하여 값을 비교하고, 비교 함수 comp를 지정할 수도 있음

- <algorithm>에 정의되어 있음

 

 

∙ 순차 탐색과 이진 탐색 구현 함수 코드

#include <iostream>
#include <algorithm>

bool linear_search(int data[], int n, int target)
{
    for (int i = 0; i < n; i++){
        if (data[i] == target)
            return true;
    }
    return false;
}

bool binary_search(int data[], int n, int target)
{
    int lower = 0;
    int upper = n - 1;
    
    if (data[lower] > target || data[upper] < target)
        return false;
    
    while (lower <= upper){
        int mid = (lower + upper) / 2;
        
        if (data[mid] == target)
            return true;
        else if (data[mid] < target)
            lower = mid + 1;
        else
            upper = mid - 1;
    }
    return false;
}

int main()
{
    int data[] = {1, 2, 3, 5, 7,10, 13, 15, 18, 23, 27, 28, 30, 33};
    int target = 23;
    
    bool res1 = linear_search(data,std::size(data), target);
    bool res2 = binary_search(data, std::size(data), target);
    bool res3 = std::binary_search(std::begin(data), std::end(data), target);
    
    std::cout << res1 << std::endl;
    std::cout << res2 << std::endl;
    std::cout << res3 << std::endl;
}