首页 > 代码库 > 算法:折半查找法

算法:折半查找法

  输入代码:

/*
 * Copyright (c) 2014, 烟台大学计算机学院
 * All rights reserved.
 * 文件名称:sum123.cpp
 * 作    者:林海云
 * 完成日期:2015年1月12日
 * 版 本 号:v2.0
 *
 * 问题描述:给定一个排序好的数组,使他可以具备查找功能
 * 输入描述:要查找的数
 * 程序输出:查找数的位置
 */
#include<iostream>
using namespace std;
const int n=10;
int main()
{
    int a[n]= {1,2,3,4,5,6,7,8,9,10} ;
    int left,right,mid,x;
    left=0;
    right=n-1;
    while(cin>>x&&left<=right)
    {
        mid=(left+right)/2;
        if(a[mid]==x)
        {
            cout<<"查到数字为a["<<mid<<"]"<<endl;
        }
        if(a[mid]<x)
        {
            left=mid+1;
        }
        else
        {
            right=mid-1;
        }
    }
    return 0;
}

运行结果:

技术分享


总结:

此算法查找的依据是从左往右依次查找,用一个while语句控制的循环实现,在mid的left处就加1继续查找,在右边的就减1继续查找,直到找到为止。

算法:折半查找法