자료구조_13.탐색(1)

 

탐색이란

---

여러 개의 자료 중에서 원하는 자료를 찾는 작업입니다.

컴퓨터가 가장 많이 하는 작업중의 하나이기에

탐색을 효율적으로 수행하는 것은 매우 중요합니다

 

 

이진탐색

---

이진 탐색의 탐색 방식

 

 

이진탐색은 우선 시작과 끝의 합을 나누기 2 해서 중앙값를 찾습니다.

그리고 구한 중앙값을 타겟과 비교하여 타겟보다 큰 경우 미드를 시작으로 하여 

미드보다 큰 값중에서 또 타겟을 찾습니다.

(작은경우 끝으로 바꿈)

위의 GIF를 기준으로 설명하자면

미드인 4와 타겟인 5를 비교하면 5가 더 크기에

시작값을 4에 1을 더한 5로 바꿉니다 그 이후 

미드인 7과 5를 비교합니다.

미드값이 타겟보다 크기에 끝을 6으로 바꿉니다.그 다음

미드인5와 5를 비교하여 같기 때문에 탐색이 완료되는 상황입니다.

 

이진탐색의 단점은 꼭 정렬이 되어있어야 한다는 점입니다.

 

시간 복잡도는 O(log N)입니다.

 

순차탐색

---

순차탐색의 탐색방식

 

순차탐색은 타겟으로 들어온 숫자를 배열을 돌면서 찾는

아주 기본적인 탐색입니다.

 

순차탐색은 꼭 정렬이 되어있지 않아도 되지만 타겟의 위치가

뒤에 있으면 뒤에 있을수록 걸리는 시간이 더 늘어난다는 점이 있습니다.

 

시간복잡도는 O(n)입니다.

 

---

이진탐색의 코드 구현

 

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; // 탐색 실패
}

 

 

---

LowerBound와 UpperBound

lowerBound와 upperBound는

#include<algorithm>에 들어있습니다.

 

이분탐색을 기반으로 작동합니다.

lowerBound는 찾고자 하는 값 이상의 수가 처음 나오는 위치 주소 반환하고

upeeround는 찾고자 하는 값보다 큰 값의 첫번째 위치 주소 반환합니다.