本文共 822 字，大约阅读时间需要 2 分钟。

二分查找

时间复杂度：O(logn)

/*给定一个无穷数组，前n个元素都是整数且已排好顺序, n的值未知，其余元素为∞。*/#include 
   
    #include 
    
     using namespace std;bool bSearch(int data[], int head, int tail, int x);int at = 0;	//记录元素x的位置int main(){	int data[15] = { 0 ,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, INT_MAX, INT_MAX, INT_MAX, INT_MAX };		//输入要查找的值	int x;	cin >> x;	int n = 0;		//记录有序的元素个数	while (data[n] != INT_MAX)	{		++n;	}	//判断是否找到该元素	if (bSearch(data, 0, n - 1, x))	{		cout << at << endl;	}	else	{		cout << INT_MAX << endl;	}	return 0;}bool bSearch(int data[], int head, int tail, int x){	int mid = (head + tail) / 2;	//找到x，记录其位置，返回主函数	if (data[mid] == x)	{		at = mid;		return 1;	}	//没有找到x，继续进行二分查找，判断head与tail的关系	if (head != tail)	{		if (data[mid] > x)		{			bSearch(data, head, mid - 1, x);		}		else		{			bSearch(data, mid + 1, tail, x);		}	}	else	{		return 0;	}}
    
   

转载地址：http://fttai.baihongyu.com/