二分法查找相对于顺序查找，有较高的效率，但前提条件是一个排好序的数组。排序的方法很多，其中效率较高的是快速排序方法：
实例代码如下：
先是产生一个随机数组，然后快速排序，最后是二分法查找：
运行结果：
input the key to look for, between 0 and 16:12 the array from which to look for: 7 15 15 7 4 2 8 11 1 14 7 10 12 10 14 3 1 2 3 4 7 7 7 8 10 10 11 12 14 14 15 15 The key is in the array!
我们知道，如果是k个元素的数组，对于顺序查找，时间复杂度是n，而二分法查找的时间复杂度只有：
如一个16个元素的数组，对于顺序查找，最坏的情况是需要比较16次，而用二分法查找，最坏的情况比较4次即可确认。
附代码：
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
const unsigned int k = 15;
void Swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
int Partition(int A[], int left, int right) // 划分函数
{
int pivot = A[right]; // 这里每次都选择最后一个元素作为基准
int tail = left - 1; // tail为小于基准的子数组最后一个元素的索引
for (int i = left; i < right; i++) // 遍历基准以外的其他元素
{
if (A[i] <= pivot) // 把小于等于基准的元素放到前一个子数组末尾
{
Swap(A, ++tail, i);
}
}
Swap(A, tail + 1, right);
// 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
// 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
return tail + 1; // 返回基准的索引
}
void QuickSort(int A[], int left, int right)
{
if (left >= right)
return;
int pivot_index = Partition(A, left, right); // 基准的索引
QuickSort(A, left, pivot_index - 1);
QuickSort(A, pivot_index + 1, right);
}
void main()
{
int key;
cout<<"input the key to look for, between 0 and "<<k<<":";
cin>>key;
cout << "the array from which to look for:"<<endl;
int arr[k];
srand(time(NULL));
for(int i=0; i<k; ++i)
{
arr[i] = rand()%16;
cout<<arr[i]<<" ";
}
cout<<endl;
int n = sizeof(arr) / sizeof(int);
QuickSort(arr, 0, n - 1);
for(i=0; i<k; ++i)
{
cout<<arr[i]<<" ";
}
cout<<endl;
int low = 0;
int high = k-1;
while(low<=high)
{
int mid = (low + high)/2;
if(key == arr[mid])
{
cout<<"The key is in the array!"<<endl;
break;
}
else
{
if(key<arr[mid])
high = mid - 1;
else
low = mid + 1;
}
}
if (low >= high)
cout<<"It’s not in the array"<<endl;
cin.get();cin.get();
}
－End－