首页 > 其他分享 >01-复杂度3 二分查找 陈越、何钦铭数据结构

01-复杂度3 二分查找 陈越、何钦铭数据结构

时间:2024-07-22 14:57:56浏览次数:14  
标签:arr 01 何钦铭 search 陈越 right Position left center

题目

可以满分通过的答案:
`
Position BinarySearch(List L, ElementType X){
Position left = 1;
Position right = L->Last;

while(left<=right){
    Position center = (left+right)/2;
    if(L->Data[center]>X){
        right = center-1;
    }else if(L->Data[center]<X){
        left = center+1;
    }else{
        return center;
    }
}
return NotFound;

}`

期间我发现,若利用递归,处理不当存在超时现象:

`Position search(ElementType arr[], ElementType X, Position left, Position right)
{
if(right == left){
if(arr[right] != X){
return NotFound;
}else{
return right;
}
}
Position center = (left+right)/2;
if(arr[center] > X){
search(arr,X,left,center);
}else if(arr[center] < X){
search(arr,X,center,right);
}else{
return center;
}
}

Position BinarySearch(List L, ElementType X){
return search(L->Data,X,1,L->Last);
}
`

`
Position search(ElementType arr[], ElementType X, Position left, Position right)
{
if(right == left){
if(arr[right] != X){
return NotFound;
}else{
return right;
}
}
Position center = (left+right)/2;
if(arr[center] > X){
search(arr,X,left,center-1);
}else if(arr[center] < X){
search(arr,X,center+1,right);
}else{
return center;
}
}

Position BinarySearch(List L, ElementType X){
return search(L->Data,X,1,L->Last);
}
`

递归改用这样即可不超时:
`
Position search(ElementType arr[], ElementType X, Position left, Position right)
{
if(right<left){
return NotFound;
}
Position center = (left+right)/2;
if(arr[center] > X){
search(arr,X,left,center-1);
}else if(arr[center] < X){
search(arr,X,center+1,right);
}else{
return center;
}
}

Position BinarySearch(List L, ElementType X){
return search(L->Data,X,1,L->Last);
}
`

标签:arr,01,何钦铭,search,陈越,right,Position,left,center
From: https://www.cnblogs.com/poyo/p/18316009

相关文章

  • 01-Scala开发环境搭建
    Scala开发环境搭建1.安装JDK:https://www.oracle.com/java/technologies/javase/javase8-archive-downloads.html2.IDEA安装Scala插件3.添加Scala的全局的Libraries4.打印HelloWorldTips:Scala中为什么要在object中才能使用Main方法?Scala中将“静态”与“类”区分的......
  • 2101. 引爆最多的炸弹 Medium
    给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。炸弹用一个下标从 0 开始的二维整数数组 bombs 表示,其中 bombs[i]=[xi,yi,ri] 。xi 和 yi 表示第 i 个炸弹的X和Y坐标,ri 表示爆炸范围的 半径 。你需要选择引爆 一个 炸弹。当......
  • 等保测评与ISO27001认证的区别全解析
    等保测评与ISO27001认证的区别全解析问题:等保测评与ISO27001认证有什么区别?回答:等保测评和ISO27001认证都是信息安全领域的重要标准,但它们在适用范围、标准要求、实施流程等方面存在显著差异。以下是详细解析:1.适用范围等保测评(信息安全等级保护):适用对象:主要适用于......
  • Metasploit Pro 4.22.2-2024071501 (Linux, Windows) - 专业渗透测试框架
    MetasploitPro4.22.2-2024071501(Linux,Windows)-专业渗透测试框架Rapid7Penetrationtesting,releaseJul15,2024请访问原文链接:https://sysin.org/blog/metasploit-pro-4/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org世界上最广泛使用的渗透测试框架......
  • [CISCN 2019 初赛]Love Math
    进入之后直接就是源码<?php//关闭所有错误报告,以防止将敏感信息泄露给用户error_reporting(0);//检查是否传入了GET参数'c'//如果没有传入,则显示当前文件的源代码if(!isset($_GET['c'])){show_source(__FILE__);}else{//读取GET参数'c'的值到$c......
  • Java基础面试题大全 -001
    1、Java语言有哪些特点1、简单易学、有丰富的类库2、面向对象(Java最重要的特性,让程序耦合度更低,内聚性更高)3、与平台无关性(JVM是Java跨平台使用的根本)4、可靠安全5、支持多线程6、java生态完善2、面向对象和面向过程的区别面向过程:是分析解决问题的步骤,然后用函数......
  • 《深入了解 MEMS LVCMOS 振荡器 SiT2001 系列(1 to 110 MHz)》
    在当今的电子领域,高性能的振荡器对于确保系统的稳定运行和精确计时至关重要。今天,我们将深入探讨一款引人注目的产品——MEMSLVCMOS振荡器SiT2001系列(1to110MHz)。一、SiT2001系列的基本概述MEMSLVCMOS振荡器SiT2001系列涵盖了1至110MHz的广泛频率范围,为......
  • [NOIP2012 普及组] 摆花(含代码)
    [NOIP2012普及组]摆花题目描述小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共mmm盆。通过调查顾客的喜好,小明列出了顾客最喜欢的......
  • 0201-金属反射和模糊
    环境Time2022-11-16WSL-Ubuntu22.04Rust1.65.0前言说明参考:https://raytracing.github.io/books/RayTracingInOneWeekend.html目标新增金属材质,实现反射和模糊函数。金属材质pubstructMetal{albedo:Color,//模糊属性fuzz:f64,}implMetal......
  • (82)DC命令--->(01)DC综合命令
    1目录(a)IC简介(b)数字IC设计流程(c)Verilog简介(d)DC综合命令(e)结束1IC简介(a)在IC设计中,设计师使用电路设计工具(如EDA软件)来设计和模拟各种电路,例如逻辑电路、模拟电路、数字信号处理电路等。然后,根据设计电路的规格要求,进行布局设计和布线,确定各个电路元件的位置和连线方式。......