在数组中搜索元素的一般方法是使用一个for循环来遍历数组中的元素。例如，下面的代码将搜索数组中的元素x：
int findNum(int a[], int len,int x)
{
int i;
for(i = 0; i < len; i++)
if( a[i] == x)
return 1; // 表示找到
return 0;
}完整代码：
#include <iostream>
using namespace std;
int findNum(int a[], int len,int x)
{
int i;
for(i = 0; i < len; i++)
if( a[i] == x)
return 1; // 表示找到
return 0;
}
int main()
{
int array[] = {2,5,1,67,34,21,78};
int len = sizeof(array) / sizeof(int);
int x;
cout << "input x:"; cin >> x;
if(findNum(array,len,x)== 1)
cout << x << " find! " << endl;
else cout << x << " not find! " << endl;
return 0;
}这种方法的时间复杂度是O (n)，因为在最坏的情况下，有必要检查数组中的所有元素。如果元素的顺序是任意的，这也是最好的方法，因为在数组中没有我们应该在什么地方搜索元素x的附加信息。
但是，如果对数组进行了排序，那么情况就不同了。在这种情况下，可以更快地执行搜索，因为数组中元素的顺序会指导搜索。下面的折半搜索算法在O（logn）时间内有效地搜索已排序数组中的一个元素。
方法一：
实现折半查找的通常方法类似于在字典中寻找一个单词。搜索将在数组中维护一个活动区域，该区域最初包含所有数组元素。然后，执行一些步骤，每个步骤都是区域大小的一半。在每一步中，搜索都会检查活动区域的中间元素。如果中间的元素是目标元素，则搜索将终止。否则，搜索递归地继续到区域的左或右半部分，这取决于中间元素的值。
int binarySearch(int a[], int len,int x)
{
int i = 0, j = len -1;
while(i <= j)
{
int k = ( i + j) / 2; //中间位置的下标
if(a[k] == x)
{ return 1;}
if(a[k] > x) j = k - 1;
else i = k + 1;
}
return 0;
}完整代码：
#include <iostream>
#include <algorithm>
using namespace std;
int binarySearch(int a[], int len,int x)
{
int i = 0, j = len -1;
while(i <= j)
{
int k = ( i + j) / 2; //中间位置的下标
if(a[k] == x)
{ return 1;}
if(a[k] > x) j = k - 1;
else i = k + 1;
}
return 0;
}
int main()
{
int array[] = {2,5,1,67,34,21,78};
int len = sizeof(array) / sizeof(int);
int x;
cout << "input x:"; cin >> x;
sort(array,array + len) ; //排序
if(binarySearch(array,len,x)== 1)
cout << x << " find! " << endl;
else cout << x << " not find! " << endl;
return 0;
}说明：
在这个实现中，活动区域是一个i……j，初始区域是0…n−1。该算法在每一步中都将区域的大小减半，因此时间复杂度为O（logn）。
方法二：
实现折半查找的另一种方法是基于一种迭代数组元素的有效方法。其想法是，当我们接近目标元素时，进行跳跃并减缓速度。
搜索从左到右穿过数组，初始跳转长度为n/2。在每一步中，跳跃的长度将被减半：先是n/4，然后是n/8，n/16，等等，直到最后长度为1。跳转之后，要么找到目标元素，或者我们知道它没有出现在数组中。
函数定义如下：
int binarySearch(int a[], int len,int x)
{
int k = 0;
for(int b = len / 2; b >= 1; b /= 2)
{
while( k+b < len && a[k + b] <= x ) k += b; //注意这里
}
if(a[k] == x)
return 1;
return 0;
}完整代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int binarySearch(int a[], int len,int x)
{
int k = 0;
for(int b = len / 2; b >= 1; b /= 2)
{
while( k+b < len && a[k + b] <= x ) k += b;
}
if(a[k] == x)
return 1;
return 0;
}
int main()
{
int array[] = {2,5,1,67,34,21,78};
int len = sizeof(array) / sizeof(int);
int x;
cout << "input x:"; cin >> x;
sort(array,array + len) ; //排序
if(binarySearch(array,len,x)== 1)
cout << x << " find! " << endl;
else cout << x << " not find! " << endl;
return 0;
}在搜索过程中，变量b包含当前的跳转长度。该算法的时间复杂度为O（logn），因为当跳转循环中的代码对每个跳转长度最多执行两次。
C++标准库包含以下基于折半查找和在对数时间内工作的函数：
- lower_bound：返回一个指向其值至少为x的第一个数组元素的指针。
- upper_bound：返回一个指向其值大于x的第一个数组元素的指针。
- equal_range： 返回以上两个指针。
这些函数假定该数组是已排序的。如果没有这样的元素，指针将指向最后一个数组元素之后的元素。例如，下面的代码将查找一个数组是否包含值为x的元素：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int array[] = {2,5,1,67,34,21,78};
int len = sizeof(array) / sizeof(int);
int x;
cout << "input x:"; cin >> x;
sort(array,array + len) ; //排序
auto k = lower_bound(array, array + len, x) - array; //其值至少为x的第一个数组元素的下标位置
if(k < len && array[k] == x)
cout << x << " find!" << endl;
else
cout << x << "not find!" << endl;
return 0;
}可以通过lower_bound和upper_bound计算元素值x的个数。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int array[] = {2,5,1,67,2,21,78};
int len = sizeof(array) / sizeof(int);
int x;
cout << "input x:"; cin >> x;
sort(array,array + len) ; //排序
auto i = lower_bound(array, array + len, x) ; //其值至少为x的第一个数组元素的地址
auto j = upper_bound(array,array +len, x) ; //返回一个指向其值大于x的第一个数组元素的地址
cout << x << "个数:" << j - i << endl;
return 0;
}也可以使用 equal_range计算元素值x的个数。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int array[] = {2,5,1,67,2,21,78};
int len = sizeof(array) / sizeof(int);
int x;
cout << "input x:"; cin >> x;
sort(array,array + len) ; //排序
auto y = equal_range(array, array + len, x);
cout << x << "个数:" << y.second -y.first << endl;
return 0;
}