[알고리즘] 선형검색(linear search)

[알고리즘] 선형검색(linear search)

선형검색(탐색)은 주어진 데이터에서 앞에서부터 순차적으로 

원하는 값을 찾는 방식입니다.

그렇기 때문에 시간복잡도는 O(n)이 됩니다.

구현이 매우 간단하지만, 

많은 데이터에서 검색을 하기에는 좀 부담이 되는 알고리즘 입니다.

데이터가 많을 때에는 이진이나 헤시 탐색등(logN)을 이용하는게 좋습니다.

< [5, 2, 13, 1, 8] 에서 1을 검색하는 과정 >

< 선형검색 코드 >

#include 
using namespace std;

// Using while
int linearSearch(int arr[], int length, int target)
{
	int nIndex = 0;
	while(nIndex < length)
	{
		if(arr[nIndex] == target)
			return arr[nIndex];
		nIndex++;
	}

	return -1;
}

int linearSearchWithFor(int arr[], int length, int target)
{
	for(int nIndex = 0; nIndex < length; nIndex++)
	{
		if(arr[nIndex] == target) return arr[nIndex];
	}

	return -1;
}

int main()
{	
	int arr[] = {5, 2, 13, 1, 8, 55, 29, 33};
	int target = 33;

	int nFound = linearSearch(arr, 8, target);

	if(nFound >= 0)
	{
		cout << "Found!!" << endl;
	}
	else
	{
		cout << "Not found!!" << endl;
	}

	return 0;
}