线性查找与二分查找

线性查找

思路：从头到尾把数组遍历一遍，直到找到关键值。

时间复杂度：O（n）

代码：

#include<iostream>
using namespace std;
template<typename T>
void linearSearch(const T* const array,int size,T keyValue){
	for(int i=0;i<size;i++){
		if(array[i]==keyValue){
			cout<<"position:"<<i<<endl;
			return ;
		}
	}
	cout<<"Not found the keyVaule!"<<endl;
}

int main(){
	const int size=5;
	int a[size]={12,34,23,0,66};
	int key=1;
	linearSearch(a,size,key);
	return 0;
} 

 

二分查找

思路：先将数组进行排序，将关键值与数组中间的值进行比较，然后调整数组，每次查找会减少一半的元素。

时间复杂度：O（logn）

代码：

#include<iostream>//二分查找 
#include<algorithm>
using namespace std;
template<typename T>
int binarySearch(const T* const array,int size,T keyValue){
	//array[]是按升序排列好的数组 
	int low=0;
	int high=size-1;
	int mid=(low+high)/2;
	do{
		if(array[mid]==keyValue){
			return mid;
		}
		else if(array[mid]<keyValue){
			low=mid+1;
		}
		else{
			high=mid-1;
		}
		mid=(low+high)/2;
	}while(low<=high); 
	return -1;//如果没找到返回-1; 
}

int main(){
	const int size=10;
	int a[size]={1,2,3,10,9,8,7,6,5,4};
	sort(a,a+size);//按升序排列
	for(int i=0;i<size;i++){
		cout<<a[i]<<" ";
	} 
	int key=6;
	int location=binarySearch(a,size,key);
	cout<<endl<<location;
	if(location==-1){
		cout<<"Not found the keyValue!"<<endl;
	}
	else{
		cout<<"location:"<<location<<endl;
	}
	return 0;
}