c# 无处不在的二分搜索

2024-04-15 11:04

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

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

// C# program to implement
// the above approach
using System;
 
class GFG
{
 
// Returns location of key, or -1 if not found
static 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;
}
}
 
// This code is contributed by code_hunt. 

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

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

// C# conversion
 
// 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;
}
 
// This code is contributed by akashish__

        在 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,则这是我们实现的最坏情况输入。
这是示例:

using System;
 
public class Floor {
    // This function returns the largest value in A that is
    // less than or equal to key. Invariant: A[l] <= key and
    // A[r] > key Boundary: |r - l| = 1 Input: A[l .... r-1]
    // Precondition: A[l] <= key <= A[r]
    static 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
    static 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);
    }
 
    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        Console.WriteLine(floor(arr, arr.Length - 1, 3));
    }
}
// This code is contributed by sarojmcy2e

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

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

using System;
 
public class OccurrencesInSortedArray
{
    // Returns the index of the leftmost occurrence of the
    // given key in the array
    private static int getLeftPosition(int[] arr, int left,
                                       int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= key)
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
        return right;
    }
 
    // Returns the index of the rightmost occurrence of the
    // given key in the array
    private static int getRightPosition(int[] arr, int left,
                                        int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= key)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }
 
    // Returns the count of occurrences of the given key in
    // the array
    public static int countOccurrences(int[] arr, int key)
    {
        int left = getLeftPosition(arr, -1, arr.Length - 1, key);
        int right = getRightPosition(arr, 0, arr.Length, key);
 
        if (arr[left] == key && key == arr[right])
        {
            return right - left + 1;
        }
        return 0;
    }
 
    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 2, 2, 3, 4, 4, 5, 5 };
        int key = 2;
        Console.WriteLine(countOccurrences(arr, key)); // Output: 3
    }

示例代码 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,我们就完成了。
        下面给出的是算法的实现。 你能想出不同的实施方案吗?   

using System;
 
public class Program
{
    public static 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 fall on r, and r always
            // points to the minimum possible value)
            if (l == r)
            {
                return l;
            }
 
            m = l + (r - l) / 2;
 
            if (A[m] < A[r])
            {
                // Minimum can't be in the range
                // (m < i <= r), we can exclude A[m+1 ... r]
                r = m;
            }
            else
            {
                // Minimum must be in the range (m < i <= r),
                // we must search in A[m+1 ... r]
                l = m + 1;
            }
        }
 
        return -1;
    }
 
    public static int BinarySearchIndexOfMinimumRotatedArray(int[] A, int size)
    {
        return BinarySearchIndexOfMinimumRotatedArray(A, 0, size - 1);
    }
 
    public static void Main()
    {
        int[] A = { 6, 7, 8, 9, 1, 2, 3, 4, 5 };
        int size = A.Length;
 
        int minIndex = BinarySearchIndexOfMinimumRotatedArray(A, size);
 
        Console.WriteLine("The index of the minimum element in the rotated array is: " + minIndex);
    }

 请参阅示例测试用例 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/905641

相关文章

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

C#中的 StreamReader/StreamWriter 使用示例详解

《C#中的StreamReader/StreamWriter使用示例详解》在C#开发中,StreamReader和StreamWriter是处理文本文件的核心类,属于System.IO命名空间,本... 目录前言一、什么是 StreamReader 和 StreamWriter?1. 定义2. 特点3. 用

如何使用C#串口通讯实现数据的发送和接收

《如何使用C#串口通讯实现数据的发送和接收》本文详细介绍了如何使用C#实现基于串口通讯的数据发送和接收,通过SerialPort类,我们可以轻松实现串口通讯,并结合事件机制实现数据的传递和处理,感兴趣... 目录1. 概述2. 关键技术点2.1 SerialPort类2.2 异步接收数据2.3 数据解析2.