二分法查找C++程序

<span style="font-size:18px;">#define size 5  
  
#include<iostream>  
using namespace std;  
  
int main()  
{  
    int i,j;  
    float t,a[size];  
      
    for (i=0;i<size;i++)     //从键盘上为数组赋值  
    {  
        cout<<"a["<<i<<"]=";  
        cin>>a[i];  
    }  
  
    for (i=0;i<size-1;i++)       //使用冒泡排序法对数组按从小到大顺序排序  
        for (j=i+1;j<size;j++)  
            if (a[i]>a[j])  
            {  
                t=a[i];  
                a[i]=a[j];  
                a[j]=t;  
            }  
  
    for (i=0;i<size;i++)     //显示排序结果  
        cout<<a[i]<<" ";  
    cout<<endl;  
  
      
    int value;  
    int found;                  //找到为1，否则为0  
    int low,high,mid;     
    for (i=1;i<=3;i++) {  
        cout<<"value=";  
    cin>>value;                   //输入要查找的数据  
      
    found=0;                    //二分法（又叫折半查找法）查找数组a  
    low=0;  
    high=size-1;  
    while(low<=high)  
    {     
        mid=(high+low)/2;  
        if (a[mid]==value)  
        {  
            found=1;  
            break;  
        }  
        if (a[mid]<value)  
            low=mid+1;          //mid往右移动  
        else  
            high=mid-1;         //mid往左移动右逢源  
        }  
        if (found)              //fond的初始值为0，一旦找到，found变量被置1,引发此条件语句，从而输出找到的结果，否则告知用户找不到。  
            cout<<"The valu found at:a["<<mid<<"]="<<a[mid]<<endl;  
        else  
            cout<<"The "<<value<<" is not found!"<<endl;  
    }  
    return 0;  
} </span>

 

 

此程序已在VC++6.0上运行过。

 

二分查找的优点和缺点：：

1.虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。 
2.二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。 
3.对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。

http://blog.csdn.net/teenapple/article/details/5879157