前言

成都创新互联公司自成立以来，一直致力于为企业提供从网站策划、网站设计、成都做网站、成都网站建设、电子商务、网站推广、网站优化到为企业提供个性化软件开发等基于互联网的全面整合营销服务。公司拥有丰富的网站建设和互联网应用系统开发管理经验、成熟的应用系统解决方案、优秀的网站开发工程师团队及专业的网站设计师团队。

一、二分查找的原理

二、二分查找的代码C语言实现

总结

---

前言

不知道大家有没有听过诸葛亮问十个问题猜将士心中数字问题这个故事。传说中诸葛亮猜数的故事诸葛亮召集将士，让他们从1-1024中选出一个整数记在心里。然后诸葛亮会问他们10个问题，他们只需回答：“是”或“不是”，最终诸葛亮就能得出他们心中所想是数。如问一谋士：“你选的数大于512？”谋士答：“不是”，之后9个问题过后，诸葛亮得出谋士所选的数是1，谋士大为吃惊，这的确是他想的数。诸葛亮所使用的方法就是把1024一半一半地取，取到第十次时就是1。根据这个原理去提10个问题就能找到别人心中所想的数。而这个原理就是我下面要介绍的二分查找也叫折半查找。

---

一、二分查找的原理

1. 首先定义一个有序数组；

2.然后定义左区间left:数组下标0，和右区间:大数组下标。

3.取中间位mid:mid=(left+right)/2

4.判断mid与目标元素target的大小，一共有三种情况:

(1)若target>arr[mid]; 则将left=mid+1; 

(2)若target

(3)若target==arr[mid]; 则返回查找成功;

5.当判断循环left>right时推出循环，并且返回此数不在数组内。 

二、二分查找的代码C语言实现

int BinarySearch(int arr[],int len,int target)
{
    int left = 0;//左下标
    int right = len - 1;//右下标
    while (left<= right)
    {
        //int mid = (left + right) / 2;这样有可能会出现两个很大的数值相加超过整形范围
        int mid=(right-left)/2+left;
        if (target >arr[mid])
        {
            left = mid + 1;
        }
        else if (target< arr[mid])
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
int main()
{

    int target = 0;
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    int len = sizeof(arr) / sizeof(arr[0]);//获取数组元素个数
    scanf("%d", &target);
    int index = BinarySearch(arr, len, target);
    if (index != -1)
        printf("找到元素，下标为%d\n", index);
    else
        printf("未找到\n");
    return 0;
}

---

总结

二分查找的速度还是特别快的，但是唯一的缺点就是需要数组是有序的。初学者容易犯两个错误。第一个是判断循环的条件一定是left<=right; 第二个是误将mid的定义放在循环外边。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：C语言实现二分查找（折半查找）-创新互联
路径分享：http://scyanting.com/article/djidsj.html