順序查找與折半查找的性能比較及C++ 計時函數的介紹

順序查找和折半查找都是很常用的查找算法，他們的查找對象都是順序表。

順序查找就是按照順序表，一個一個問哎是不是你是不是你，不是就繼續問下一個直到找到為止，簡單有效的方法。時間複雜度為O(n),平均複雜度為O(n/2)，還是一個級别。

折半查找查找的前提是此順序表必須是有序的，即需要先排序，然後再查找。他的查找方法就是定區間，折中取數如果尋找的數大于這個數那麼就在右區間繼續查找，如果小于這個數就在左區間繼續查找。時間複雜度為log2（n），也就是說long long 範圍内，最多查找60多次就能找到。。。，這和順序查找完全不是一個級别的。。

看看測試程式和結果吧。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <ctime>
#define maxn 100000005
using namespace std;
int main(){
	while(1){
		long long num;
		cout<<"輸入查找的資料量："<<endl;
		cin>>num;
		long long *s=new long long[num],i=num-1;
		while(i>=0){ 
			s[i]=i;
			i--; 
		} 
		cout<<"請輸入要查找的元素："<<endl;
		long long key;
		cin>>key; 
		clock_t start1,finish1;
		start1=clock();
		for(int i=1;i<num;i++)
			if(s[i]==key)
			 	break;
		finish1=clock();
		double Cost_time1 = (double)(finish1-start1)/CLOCKS_PER_SEC;
		cout<<"順序查找所花費的時間為："<<Cost_time1<<"s"<<endl;
		clock_t start2,finish2;
		start2=clock();
		long long left=0,right=num-1,mid=(left+right)/2;
		while(left<=right){
			if(s[mid]==key)
				break;
			else if(s[mid]<key)
				right=mid-1;
			else
				left=mid+1;
			mid=(left+right)/2;
		}
		finish2=clock();
		double Cost_time2 = (double)(finish2-start2)/CLOCKS_PER_SEC;
		cout<<"順序表折半查找所花費的時間為："<<Cost_time2<<"s"<<endl;
	}
	return 0;
}
           

測試的結果為：

資料再大就要炸了~然而折半查找還是0，就那幾十次根本測不出來好麼。。。。。

然後說一下測試程式中用到的計時函數：

頭檔案： #include<ctime>

使用方法：定義兩個時間點，如 clock_t start,end;

然後分别在需要計時部分前後加上兩個函數。

start=clock();   end=clock();

最後再用一個函數就可以計算出來最終的運作時間：

double Cost_time = (double)(finish-start)/CLOCKS_PER_SEC;

這個函數大概實作過程就是，定義兩個點，分别在計時部分開始前和開始後擷取一個時間點，但是這個時間不是我們通常意義上的時間，而是一種類似于運作次數之類的，然後除以CPU有關的數，得出來的就是時間。是不是s不太确定，但是可以反映程式運作的快慢了~