热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

排序数组中天花板的C#程序

排序数组中天花板的C#程序原文:https://www.

排序数组中天花板的 C# 程序

原文:https://www . geeksforgeeks . org/cs harp-program-for-child-in-a-sorted-array/

给定一个已排序的数组和值 x,x 的上限是数组中大于或等于 x 的最小元素,下限是小于或等于 x 的最大元素,假设数组按非递减顺序排序。写高效函数求楼层和天花板的 x.
例:

For example, let the input array be {1, 2, 8, 10, 10, 12, 19}
For x = 0: floor doesn't exist in array, ceil = 1
For x = 1: floor = 1, ceil = 1
For x = 5: floor = 2, ceil = 8
For x = 20: floor = 19, ceil doesn't exist in array

在下面的方法中,我们只实现了上限搜索功能。楼层搜索也可以用同样的方式实现。
方法 1(线性搜索)
搜索 x 上限的算法:
1)如果 x 小于或等于数组中的第一个元素,则返回 0(第一个元素的索引)
2)否则线性搜索索引 I,使 x 位于 arr[i]和 arr[i+1]之间。
3)如果在步骤 2 中没有找到索引 I,则返回-1

C


// C# program to find celing
// in a sorted array
using System;
class GFG {
    // Function to get index of ceiling 
    // of x in arr[low..high] 
    static int ceilSearch(int[] arr, int low, 
                           int high, int x)
    {
        int i;
        // If x is smaller than or equal
        // to first element, then return
        // the first element 
        if (x <= arr[low])
            return low;
        // Otherwise, linearly search 
        // for ceil value 
        for (i = low; i < high; i++) {
            if (arr[i] == x)
                return i;
            /* if x lies between arr[i] and 
            arr[i+1] including arr[i+1], 
            then return arr[i+1] */
            if (arr[i] < x && arr[i + 1] >= x)
                return i + 1;
        }
        /* If we reach here then x is 
        greater than the last element 
        of the array, return -1 in 
        this case */
        return -1;
    }
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
        int n = arr.Length;
        int x = 3;
        int index = ceilSearch(arr, 0, n - 1, x);
        if (index == -1)
            Console.Write("Ceiling of " + x +
                     " doesn't exist in array");
        else
            Console.Write("ceiling of " + x +
                         " is " + arr[index]);
    }
}
// This code is contributed by Sam007.

输出:

ceiling of 3 is 8

时间复杂度: O(n)
方法 2(二分搜索法)
这里不用线性搜索,而是用二分搜索法来找出索引。二分搜索法将时间复杂度降低到 0(Logn)。

C


// C# program to find celing
// in a sorted array
using System;
class GFG {
    // Function to get index of ceiling
    // of x in arr[low..high]
    static int ceilSearch(int[] arr, int low, 
                             int high, int x)
    {
        int mid;
        // If x is smaller than or equal 
        // to the first element, then 
        // return the first element.
        if (x <= arr[low])
            return low;
        // If x is greater than the last 
        // element, then return -1 
        if (x > arr[high])
            return -1;
        // get the index of middle  
        // element of arr[low..high]
        mid = (low + high) / 2; 
        // low + (high - low)/2 
        // If x is same as middle  
        // element then return mid 
        if (arr[mid] == x)
            return mid;
        // If x is greater than arr[mid],  
        // then either arr[mid + 1] is
        // ceiling of x or ceiling lies
        // in arr[mid+1...high] 
        else if (arr[mid] < x) {
            if (mid + 1 <= high && x <= arr[mid + 1])
                return mid + 1;
            else
                return ceilSearch(arr, mid + 1, high, x);
        }
        // If x is smaller than arr[mid], 
        // then either arr[mid] is ceiling 
        // of x  or ceiling lies in 
        // arr[low...mid-1] 
        else {
            if (mid - 1 >= low && x > arr[mid - 1])
                return mid;
            else
                return ceilSearch(arr, low, mid - 1, x);
        }
    }
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
        int n = arr.Length;
        int x = 8;
        int index = ceilSearch(arr, 0, n - 1, x);
        if (index == -1)
            Console.Write("Ceiling of " + x +
                      " doesn't exist in array");
        else
            Console.Write("ceiling of " + x + 
                            " is " + arr[index]);
    }
}
// This code is contributed by Sam007.

输出:

Ceiling of 20 doesn't exist in array

时间复杂度:O(Logn)

相关文章:
排序数组中的 floor
在未排序数组中查找 Floor 和 ceil
如果您发现以上代码/算法中有任何一个不正确,或者找到更好的方法来解决相同的问题,或者想要为 Floor 实现共享代码,请写评论。

更多详情请参考完整文章排序数组中的上限!


推荐阅读
  • 在尝试对 QQmlPropertyMap 类进行测试驱动开发时,发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的,需要进一步研究以找到解决方案。 ... [详细]
  • Ihavetwomethodsofgeneratingmdistinctrandomnumbersintherange[0..n-1]我有两种方法在范围[0.n-1]中生 ... [详细]
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 检查在所有可能的“?”替换中,给定的二进制字符串中是否出现子字符串“10”带 1 或 0 ... [详细]
  • 开机自启动的几种方式
    0x01快速自启动目录快速启动目录自启动方式源于Windows中的一个目录,这个目录一般叫启动或者Startup。位于该目录下的PE文件会在开机后进行自启动 ... [详细]
  • 本文介绍了一种使用 JavaScript 计算两个日期之间时间差的方法。该方法支持多种时间格式,并能返回秒、分钟、小时和天数等不同精度的时间差。 ... [详细]
  • 字符串学习时间:1.5W(“W”周,下同)知识点checkliststrlen()函数的返回值是什么类型的?字 ... [详细]
  • 在多线程并发环境中,普通变量的操作往往是线程不安全的。本文通过一个简单的例子,展示了如何使用 AtomicInteger 类及其核心的 CAS 无锁算法来保证线程安全。 ... [详细]
  • 文章目录Golang定时器Timer和Tickertime.Timertime.NewTimer()实例time.AfterFunctime.Tickertime.NewTicke ... [详细]
  • 本文介绍了一种在ANSI C中动态分配二维数组的方法。通过创建指针数组并为每个指针分配连续空间,可以灵活地管理内存。文章还讨论了一些常见的错误和注意事项。 ... [详细]
  • 在软件开发过程中,经常需要将多个项目或模块进行集成和调试,尤其是当项目依赖于第三方开源库(如Cordova、CocoaPods)时。本文介绍了如何在Xcode中高效地进行多项目联合调试,分享了一些实用的技巧和最佳实践,帮助开发者解决常见的调试难题,提高开发效率。 ... [详细]
  • 本文详细解析了客户端与服务器之间的交互过程,重点介绍了Socket通信机制。IP地址由32位的4个8位二进制数组成,分为网络地址和主机地址两部分。通过使用 `ipconfig /all` 命令,用户可以查看详细的IP配置信息。此外,文章还介绍了如何使用 `ping` 命令测试网络连通性,例如 `ping 127.0.0.1` 可以检测本机网络是否正常。这些技术细节对于理解网络通信的基本原理具有重要意义。 ... [详细]
  • 如何将TS文件转换为M3U8直播流:HLS与M3U8格式详解
    在视频传输领域,MP4虽然常见,但在直播场景中直接使用MP4格式存在诸多问题。例如,MP4文件的头部信息(如ftyp、moov)较大,导致初始加载时间较长,影响用户体验。相比之下,HLS(HTTP Live Streaming)协议及其M3U8格式更具优势。HLS通过将视频切分成多个小片段,并生成一个M3U8播放列表文件,实现低延迟和高稳定性。本文详细介绍了如何将TS文件转换为M3U8直播流,包括技术原理和具体操作步骤,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 利用 JavaScript 和 Node.js 验证时间的有效性
    本文探讨了如何使用 JavaScript 和 Node.js 验证时间的有效性。通过编写一个 `isTime` 函数,我们可以确保输入的时间格式正确且有效。该函数利用正则表达式匹配时间字符串,检查其是否符合常见的日期时间格式,如 `YYYY-MM-DD` 或 `HH:MM:SS`。此外,我们还介绍了如何处理不同时间格式的转换和验证,以提高代码的健壮性和可靠性。 ... [详细]
  • 本文全面解析了 Python 中字符串处理的常用操作与技巧。首先介绍了如何通过 `s.strip()`, `s.lstrip()` 和 `s.rstrip()` 方法去除字符串中的空格和特殊符号。接着,详细讲解了字符串复制的方法,包括使用 `sStr1 = sStr2` 进行简单的赋值复制。此外,还探讨了字符串连接、分割、替换等高级操作,并提供了丰富的示例代码,帮助读者深入理解和掌握这些实用技巧。 ... [详细]
author-avatar
xsf9507
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有