`
lt200819
  • 浏览: 187538 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

二分查找算法学习札记

 
阅读更多

二分查找算法学习札记
说明
作者:那谁
blog: http://www.cppblog.com/converse
转载请注明出处.
二分查找算法基本思想
二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.

用伪代码来表示, 二分查找算法大致是这个样子的:

left = 0, right = n -1
while (left <= right)
    mid = (left + right) / 2
    case
        x[mid] < t:    left = mid + 1;
        x[mid] = t:    p = mid; break;
        x[mid] > t:    right = mid -1;

return -1;

 

下面,讲讲在编写二分查找算法时可能出现的一些问题.

边界错误造成的问题
二分查找算法的边界,一般来说分两种情况,一种是左闭右开区间,类似于[left, right),一种是左闭右闭区间,类似于[left, right].需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.比如下面就是错误的二分查找算法:

int search_bad(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n;

    while (left < right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            right = middle - 1;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}


这个算法的错误在于, 在循环初始化的时候,初始化right=n,也就是采用的是左闭右开区间,而当满足array[middle] > v的条件是, v如果存在的话应该在[left, middle)区间中,但是这里却把right赋值为middle - 1了,这样,如果恰巧middle-1就是查找的元素,那么就会找不到这个元素.
下面给出两个算法, 分别是正确的左闭右闭和左闭右开区间算法,可以与上面的进行比较:

int search2(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n - 1;

    while (left <= right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            right = middle - 1;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

int search3(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n;

    while (left < right)
    {
        middle = (left + right) / 2;

        if (array[middle] > v)
        {
            right = middle;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}



死循环
上面的情况还只是把边界的其中一个写错, 也就是右边的边界值写错, 如果两者同时都写错的话,可能会造成死循环,比如下面的这个程序:

int search_bad2(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n - 1;

    while (left <= right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            right = middle;
        }
        else if (array[middle] < v)
        {
            left = middle;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}


这个程序采用的是左闭右闭的区间.但是,当array[middle] > v的时候,那么下一次查找的区间应该为[middle + 1, right], 而这里变成了[middle, right];当array[middle] < v的时候,那么下一次查找的区间应该为[left, middle - 1], 而这里变成了[left, middle].两个边界的选择都出现了问题, 因此,有可能出现某次查找时始终在这两个范围中轮换,造成了程序的死循环.

溢出
前面解决了边界选择时可能出现的问题, 下面来解决另一个问题,其实这个问题严格的说不属于算法问题,不过我注意到很多地方都没有提到,我觉得还是提一下比较好.
在循环体内,计算中间位置的时候,使用的是这个表达式:

middle = (left + right) / 2;


假如,left与right之和超过了所在类型的表示范围的话,那么middle就不会得到正确的值.
所以,更稳妥的做法应该是这样的:

middle = left + (right - left) / 2;


更完善的算法
前面我们说了,给出的第一个算法是一个"正确"的程序, 但是还有一些小的问题.
首先, 如果序列中有多个相同的元素时,查找的时候不见得每次都会返回第一个元素的位置, 比如考虑一种极端情况:序列中都只有一个相同的元素,那么去查找这个元素时,显然返回的是中间元素的位置.
其次, 前面给出的算法中,每次循环体中都有三次情况,两次比较,有没有办法减少比较的数量进一步的优化程序?
<<编程珠玑>>中给出了解决这两个问题的算法,结合前面提到溢出问题我对middle的计算也做了修改:

int search4(int array[], int n, int v)
{
    int left, right, middle;

    left = -1, right = n;

    while (left + 1 != right)
    {
        middle = left + (right - left) / 2;

        if (array[middle] < v)
        {
            left = middle;
        }
        else
        {
            right = middle;
        }
    }

    if (right >= n || array[right] != v)
    {
        right = -1;
    }

    return right;
}


这个算法是所有这里给出的算法中最完善的一个,正确,精确且效率高.
参考资料
1.<<编程珠玑>>
2.wiki上关于二分查找的说明:http://en.wikipedia.org/wiki/Binary_search

分享到:
评论

相关推荐

    labview 学习札记2

    本学习札记的第二卷,将深入介绍LabVIEW的基本概念和核心功能,旨在帮助初学者快速入门。以下是可能涵盖的知识点: 1. **G语言**:LabVIEW的核心编程语言称为G语言,通过拖拽和连接不同的函数框图来实现代码编写。G...

    LabView学习札记

    PDF文件包含了学习札记的序言和五个章节,分别是“一(上)、一(下)、二、三(上)、三(下)”。这些章节可能涵盖了LabView的基础知识,如G语言基础、界面设计、数据处理、控制流与结构以及可能深入到的高级主题...

    labview学习札记

    LabVIEW(Laboratory Virtual Instrument Engineering Workbench)是一种图形化编程环境,主要用于开发虚拟...希望这个学习札记能帮助你在虚拟仪器的学习道路上找到方向,不断进步,最终在LabVIEW的世界里游刃有余。

    Simulink代码生成学习札记[汇编].pdf

    Simulink代码生成学习札记[汇编].pdf

    LabVIEW学习札记

    这个“LabVIEW学习札记”显然是一份关于掌握LabVIEW核心概念和技术的详细资料。下面我们将深入探讨LabVIEW的一些关键知识点。 1. **G语言**: LabVIEW的核心编程语言称为G,它是一种基于图形的编程语言。通过连接...

    虚拟仪器LabVIEW 教程PPT资料 学习札记 应用设计等学习资料.zip

    LabVIEW_学习札记_-_第二卷.pdf LabVIEW微波测试系统.pdf labview论坛-基于Labview的智能小车控制平台.doc 基于LabVIEW的多传感器信息采集平台.pdf 基于虚拟仪器的三段式距离保护研.doc 基于虚拟仪器的液位控制系统...

    Simulink代码生成学习札记.zip

    这个“Simulink代码生成学习札记”可能包含了关于如何使用Simulink从模型直接生成可执行代码的重要知识,这对于工程师和开发者来说是一个极其有用的资源,特别是对于初学者。 Simulink的主要功能之一就是代码生成,...

    LabVIEW 学习札记 - 第一卷 上

    本札记“LabVIEW学习札记 - 第一卷 上”将带你逐步走进LabVIEW的世界,揭示其核心概念和常见问题。 首先,LabVIEW的核心在于它的G图形化编程语言。与传统的文本编程语言不同,LabVIEW使用的是图标和连线来表示程序...

    labview论坛-LabVIEW 学习札记 - 第二卷

    "LabVIEW 学习札记 - 第二卷"是针对LabVIEW进阶学习的一份珍贵资料,包含了丰富的实践案例和深入的技术解析。 在这一卷中,你可能会学习到以下几个关键知识点: 1. **G语言与程序结构**:LabVIEW的核心是G语言,一...

    二分法查找

    “二分查找学习札记.pdf”很可能包含了关于二分查找的深入分析、实例演示以及相关的编程练习,可以帮助初学者更好地理解并掌握这一算法。通过系统学习和实践,你可以逐步克服对二分查找的恐惧,提高自己的算法能力。

    公司法学习札记.pdf

    公司法学习札记.pdf

    labview 学习札记3a

    "labview 学习札记3a"显然是一个关于LabVIEW的教程资源,旨在帮助初学者掌握这个平台的基础知识,并通过实际工程实例加深理解。 在LabVIEW的学习过程中,有几个关键的知识点是必须掌握的: 1. **基本概念**:理解...

    复变函数札记

    《复变函数札记》是作者梁昌洪继《矢算场论札记》(科学出版社,2007)之后的第二本工程数学札记。尽管两书所涉及领域完全不同,但却有着完全一致的目标,即希望在数学和工程之间架设一座可以自如跨越的桥梁。对于...

    Nios II 学习札记

    【Nios II 学习札记】 Nios II 是由 Altera 公司开发的一种软核处理器,广泛应用于 FPGA(Field-Programmable Gate Array)设计中,它提供了高效的嵌入式处理解决方案。Nios II 提供了三种不同的内核类型,分别是 ...

    5-学习札记快速整理软件-使用说明书1

    学习札记快速整理软件是一款专为学习者设计的高效笔记管理工具,旨在帮助用户快速整理、记录和检索学习内容。本文将详细介绍该软件的各个功能、运行环境以及使用方法,以便用户更好地利用这款软件提升学习效率。 **...

    mysql学习札记.zip

    这份"mysql学习札记.zip"文件显然包含了作者在学习MySQL过程中积累的知识和经验,可能是笔记、示例代码或者教程。虽然没有具体的标签来细化主题,但我们可以根据常见的MySQL学习路径来探讨一些关键知识点。 首先,...

    EXT学习札记--京华志

    EXT学习札记 ExtJs学习--京华志 京华志出品 必数精华

    2-学习札记快速整理软件-项目概要1

    《学习札记快速整理软件——打造高效笔记新体验》 学习札记快速整理软件,是一款专为学生群体及需要频繁记录信息的用户设计的APP,旨在解决信息快速记录、整理和分类的难题。这款软件以创新的功能和贴心的设计,...

Global site tag (gtag.js) - Google Analytics