循序搜尋法 Linear Search

2016-01-02

5776
0
C++
2016-01-03

循序搜尋法(Linear Search)算是搜尋演算法當中比較簡單的一種，是用來達成"搜尋"目的的。

原理顧名思義就是從第一筆資料開始，依序比對每一筆資料，再來找出所需要的資料。

本文以C++實作執行。

循序搜尋法(Linear Search)會依序比對每一筆資料，所以最大搜索時間為資料大小n，最小搜索時間為1，平均搜尋時間為(n+1)/2。所以其時間複雜度為Ο(n)。

PseudoCode 大致如下:

TYPE linearSearch(TYPE  data[], TYPE  key, TYPE  size)
{
	INDEX i;

	for (i = 0; i < size; i++)
	{
		if (data[i] == key)
		{
			return i;
		}
	}
	return -1;
}

第一個參數 data是陣列名稱，第二個參數key是想要搜索的值，第三個參數size是陣列的大小。

完整程式碼如下:


#include <iostream>
using namespace std;

int linearSearch(int[], int, int);

int main() {

	const int size = 100;//陣列大小
	int search = 0;//想要找的值

	int arr[100];//初始化資料陣列

	for (int i = 0; i < size; i++)
	{
		arr[i] = 2 * i;//賦予陣列值: a[0]=0 a[1]=2 a[2]=4 ... a[99]=198
	}

	cout << "Input the value:";
	cin >> search;
	int element = linearSearch(arr, search, size);

	if (element != -1)
	{
		cout << "Found value in element " << element << endl;
	}

	else
	{
		cout << "Value not found" << endl;
	}

	system("pause");

	return 0;
}

int linearSearch(int data[], int key,int size)
{
	int index;

	for (index = 0; index < size; index++)
	{
		if (data[index]==key)
		{
			return index;
		}
	}
	return -1;
}

以下是執行結果:

有夢最美築夢踏實

活在當下認真過每一天

我是阿夢也是Ace

回首頁