[탐색] 순차 탐색, 이진 탐색

[순차 탐색 (sequential search)]

• 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법
  - 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사

 

• 평균 비교 횟수
  - 탐색 성공: (n + 1) / 2번 비교
  - 탐색 실패: n번 비교

 

<순차 탐색 알고리즘>

int sequentialSearch(int list[], int key, int low, int high)
{
	for (int i = low; i <= high; i++)
    	if (list[i] == key)
        	return i;
    return -1;
}

 

- 시간 복잡도: O(n)

 

 

 

[이진 탐색 (binary search)]

• 정렬된 배열의 탐색에 적합
  배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄여가며 탐색 진행

 

• ex) 10억명 중에서 특정한 이름 탐색
  - 이진 탐색 : 단지 30번의 비교를 필요함
  - 순차 탐색 : 평균 5억번의 비교가 필요함

 

<이진 탐색 구현>

int binarySearch (int list[], int key, int low, int high)
{
	int middle;
    while (low <= high)
    {
    	middle == (low + high) / 2;
        if (key == list[middle]) // 탐색 성공
        	return middle;
        else if (key > list[middle])
        	low = middle + 1;
        else
        	high = middle - 1;
    }
    return -1; // 탐색 실패
}

 

 

[이진 탐색 vs 순차 탐색]

• 정렬된 상태가 아니라면? 시간 복잡도를 비교해보자

 

정렬되지 않은 상태라면 이진 탐색 (Binary Search)가 더욱 효율적이다.

 

[upper_bound & lower_bound]

• #include <algorithm>을 해줘야 사용가능
• 이분 탐색을 기반으로 함
• Upper_bound : 찾고자 하는 값보다 큰 값의 첫 번째 위치 주소 반환
• Lower_bound : 찾고자 하는 값 이상의 수가 처음 나오는 위치 주소 반환
• Upper(Lower)_bound(첫 번째 주소, 마지막 + 1 주소, 찾는 수) - 이렇게 사용해야한다.

 

 

• 만약 upper_bound와 lower_bound의 차이가 0이라면, 찾는 수가 없는 것이다.
• 정렬된 배열에서 특정 수의 개수를 구하기 위해서는 upper_bound와 lower_bound의 차를 통해 계산하면 된다.

 

 

[매개변수 탐색]

• 최적화 문제를 여러 번의 결정 문제로 바꾸어서 해결하는 방법
  - 최적화 문제: 특정 조건을 만족하는 것들 중 가장 알맞은 값(최솟값, 최댓값)을 찾는 문제
  - 결정 문제: YES or NO로 답할 수 있는 문제