c 语言 无处不在的二分搜索

2024-04-17 10:52

本文主要是介绍c 语言 无处不在的二分搜索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        我们知道二分查找算法。二分查找是最容易正确的算法。我提出了一些我在二分搜索中收集的有趣问题。有一些关于二分搜索的请求。我请求您遵守准则:“我真诚地尝试解决问题并确保不存在极端情况”。阅读完每个问题后,最小化浏览器并尝试解决它。 
        问题陈述:给定一个由 N 个不同元素组成的排序数组,使用最少的比较次数在数组中找到一个键。 (您认为二分搜索是在排序数组中搜索键的最佳选择吗?)无需太多理论,这里是典型的二分搜索算法。

// Returns location of key, or -1 if not found
int BinarySearch(int A[], int l, int r, int key)
{
    int m;
 
    while( l <= r )
    {
        m = l + (r-l)/2;
 
        if( A[m] == key ) // first comparison
            return m;
 
        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }
 
    return -1;

        理论上,最坏情况下我们需要进行log N + 1次比较。如果我们观察的话,我们会在每次迭代中使用两次比较,除非最终成功匹配(如果有)。在实践中,比较将是昂贵的操作,它不仅仅是原始类型比较。尽量减少与理论极限的比较更为经济。请参阅下图,了解下一个实现中索引的初始化。 

以下实现使用较少的比较次数。 

// Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l .... r-1]
int BinarySearch(int A[], int l, int r, int key)
{
    int m;
 
    while( r - l > 1 )
    {
        m = l + (r-l)/2;
 
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
 
    if( A[l] == key )
        return l;
    if( A[r] == key )
        return r;
    else
        return -1;

        在 while 循环中,我们仅依赖于一次比较。搜索空间收敛到将l和r指向两个不同的连续元素。我们需要再进行一次比较来跟踪搜索状态。您可以查看示例测试用例 http://ideone.com/76bad0。 (C++11 代码)。

        问题陈述:给定一个由 N 个不同整数组成的数组,找到输入“key”的下限值。假设 A = {-1, 2, 3, 5, 6, 8, 9, 10} 且 key = 7,我们应该返回 6 作为结果。我们可以使用上面的优化实现来找到键的下限值。只要不变量成立,我们就不断地将左指针移到最右边。最终左指针指向小于或等于 key 的元素(根据定义下限值)。以下是可能的极端情况, —> 如果数组中的所有元素都小于 key,则左指针移动到最后一个元素。 —> 如果数组中的所有元素都大于 key,则为错误情况。 —> 如果数组中的所有元素都相等且 <= key,则这是我们实现的最坏情况输入。
这是示例: 

// largest value <= key
// Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l .... r-1]
// Precondition: A[l] <= key <= A[r]
int Floor(int A[], int l, int r, int key)
{
    int m;
 
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
 
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
 
    return A[l];
}
 
// Initial call
int Floor(int A[], int size, int key)
{
    // Add error checking if key < A[0]
    if( key < A[0] )
        return -1;
 
    // Observe boundaries
    return Floor(A, 0, size, key);

您可以看到一些测试用例 http://ideone.com/z0Kx4a。 

        问题陈述:给定一个可能有重复元素的排序数组。查找log N时间内输入“key”出现的次数。这里的想法是使用二分搜索查找数组中最左边和最右边出现的键。我们可以修改底函数来跟踪最右边的出现和最左边的出现。 
这是示例:  

// Input: Indices Range [l ... r)
// Invariant: A[l] <= key and A[r] > key
int GetRightPosition(int A[], int l, int r, int key)
{
    int m;
 
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
 
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
 
    return l;
}
 
// Input: Indices Range (l ... r]
// Invariant: A[r] >= key and A[l] > key
int GetLeftPosition(int A[], int l, int r, int key)
{
    int m;
 
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
 
        if( A[m] >= key )
            r = m;
        else
            l = m;
    }
 
    return r;
}
 
int CountOccurrences(int A[], int size, int key)
{
    // Observe boundary conditions
    int left = GetLeftPosition(A, -1, size-1, key);
    int right = GetRightPosition(A, 0, size, key);
 
    // What if the element doesn't exists in the array?
    // The checks helps to trace that element exists
    return (A[left] == key && key == A[right])?
        (right - left + 1) : 0;
}

示例代码 zn6R6a - Online C++0x Compiler & Debugging Tool - Ideone.com。 

        问题陈述: 给定一个由不同元素组成的排序数组,并且该数组在未知位置旋转。找到数组中的最小元素。我们可以在下图中看到示例输入数组的图示。

        我们收敛搜索空间直到l和r 指向单个元素。如果中间位置落在第一个脉冲中,则不满足条件 A[m] < A[r],我们将搜索空间收敛到 A[m+1 … r]。如果中间位置落在第二个脉冲中,则满足条件 A[m] < A[r],我们将搜索空间收敛到 A[1 … m]。在每次迭代中,我们都会检查搜索空间大小,如果它是 1,我们就完成了。
        下面给出的是算法的实现。 你能想出不同的实施方案吗?   

int BinarySearchIndexOfMinimumRotatedArray(int A[], int l, int r)
{
    // extreme condition, size zero or size two
    int m;
 
    // Precondition: A[l] > A[r]
    if( A[l] <= A[r] )
        return l;
 
    while( l <= r )
    {
        // Termination condition (l will eventually falls on r, and r always
        // point minimum possible value)
        if( l == r )
            return l;
 
        m = l + (r-l)/2; // 'm' can fall in first pulse,
                        // second pulse or exactly in the middle
 
        if( A[m] < A[r] )
            // min can't be in the range
            // (m < i <= r), we can exclude A[m+1 ... r]
            r = m;
        else
            // min must be in the range (m < i <= r),
            // we must search in A[m+1 ... r]
            l = m+1;
    }
 
    return -1;
}
 
int BinarySearchIndexOfMinimumRotatedArray(int A[], int size)
{
    return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1);

请参阅示例测试用例 KbwDrk - Online C++0x Compiler & Debugging Tool - Ideone.com。 

练习: 
1. 称为signum(x, y)的函数 定义为,

Signum(x, y) = -1 如果 x < y 
             = 0 如果 x = y 
             = 1 如果 x > y

您是否遇到过比较行为类似于符号函数的指令集?它能让二分搜索的第一个实现变得最优吗? 

2. 实现floor函数的ceil函数复制品。 

3. 与你的朋友讨论“二分查找是否是最优的(比较次数最少)?为什么不在排序数组上进行三元搜索或插值搜索?与二分搜索相比,您什么时候更喜欢三元搜索或插值搜索?” 

4. 画出二分搜索的树表示(相信我,这对你理解二分搜索的内部原理有很大帮助)。 

这篇关于c 语言 无处不在的二分搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/911606

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

使用Go语言开发一个命令行文件管理工具

《使用Go语言开发一个命令行文件管理工具》这篇文章主要为大家详细介绍了如何使用Go语言开发一款命令行文件管理工具,支持批量重命名,删除,创建,移动文件,需要的小伙伴可以了解下... 目录一、工具功能一览二、核心代码解析1. 主程序结构2. 批量重命名3. 批量删除4. 创建文件/目录5. 批量移动三、如何安