二分搜索是所有以比较为基础的搜索算法时间复杂度最低的算法。用二叉树描速二分查找算法,最坏情况下与二叉树的最高阶相同。比较二叉树线性查找也可用二叉树表示,最坏情况下比较次数为数组元素数量。任何一种以比较为基础的搜索算法,其最坏情况所用时间不可能低于O(logn)。
//2d3 二分搜索技术
#include "stdafx.h"
#include <iostream>
using namespace std;
template<class Type>
int BinarySearch(Type a[],const Type& x,int n);
int main()
{
int x = 6;
int a[10];
for(int i=0; i<10; i++)
{
a[i] = i + 1;
}
cout<<BinarySearch(a,x,10)<<endl;
return 0;
}
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left = 0;
int right = n-1;
while(left<=right)
{
int mid = (left + right)/2;
if(x == a[mid])
{
return mid;
}
if(x>a[mid])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}