03 折半查找

简介:   折半查找又称为二分查找。它仅适用于有序的顺序表。  折半查找的基本思想:首先给定值 key 与表中中间位置的元素比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如,在查找表升序排列时,若给定值 key 大于中间元素,则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找,如此重复,知道找到位置,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。 

 折半查找又称为二分查找。它仅适用于有序的顺序表。

 折半查找的基本思想:首先给定值 key 与表中中间位置的元素比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如,在查找表升序排列时,若给定值 key 大于中间元素,则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找,如此重复,知道找到位置,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。 

算法

typedef int ElemType;
 typedef struct MyStruct    //查找表的数据结构(顺序表)
{
  int TableLen ;    //表的长度
  ElemType* elem; //动态数组的基址
}SeqList;
 //折半查找
int Binary_Search(SeqList L, ElemType key) 
{
  int low = 0, high = L.TableLen - 1,mid;
  while (low<=high)
  {
    mid = (low + high) / 2; // 获取中间位置
    if (L.elem[mid]==key)
    {
      return mid;   //  查找成功则返回所在位置
    }
    else if(L.elem[mid]>key)
    {
      high = mid - 1;   //从前半部分继续查找
    }
    else
    {
      low = mid + 1;    //从后半部分继续查找
    }
  }
  return -1;    //查找失败,返回-1
}

算法解释

59e0c09816d646a4842ce81cf2852fbd.png

目录
相关文章
|
Kubernetes 应用服务中间件 Linux
Docker 容器编排(compose)
介绍 compose 安装和 yaml 文件编写,实现容器的批量编排。
761 1
Docker 容器编排(compose)
|
8月前
|
机器学习/深度学习 计算机视觉 iOS开发
RT-DETR改进策略【模型轻量化】| 替换骨干网络 CVPR-2024 RepViT 轻量级的Vision Transformers架构
RT-DETR改进策略【模型轻量化】| 替换骨干网络 CVPR-2024 RepViT 轻量级的Vision Transformers架构
417 0
RT-DETR改进策略【模型轻量化】| 替换骨干网络 CVPR-2024 RepViT 轻量级的Vision Transformers架构
|
3月前
|
Ubuntu Linux
Ubuntu启动提示"recovering journal"并进入紧急模式。
若您对Linux系统不太熟悉,建议寻求有经验的技术人员帮助。在大多数情况下,这些步骤将足以帮助您诊断问题,并可能恢复系统到正常工作状态,但是在极端情况下,系统可能无法修复,那时就需要考虑恢复数据和重新安装Ubuntu。所以,在日常使用中定时备份数据是非常重要的。这样可以在遇到系统崩溃时降低数据丢失的风险。
383 0
|
C语言 定位技术 API
【C语言】实践:贪吃蛇小游戏(附源码)(二)
【C语言】实践:贪吃蛇小游戏(附源码)
【C语言】实践:贪吃蛇小游戏(附源码)(二)
|
安全 Java 测试技术
最佳实践:通义灵码生成单元测试,让单测更简单
本文首先讲述了什么是单元测试、单元测试的价值、一个好的单元测试所具备的原则,进而引入如何去编写一个好的单元测试,通义灵码是如何快速生成单元测试的。
|
消息中间件 Dubbo 网络协议
中间件数据传输机制
【7月更文挑战第7天】
256 4
|
小程序 Java 数据库
8套三级医院应用的管理系统源码,直接上项目,HIS、LIS、PACS
8套应用于二级医院、三级医院医院管理系统源码,均有自主知识产权,应用案例,系统稳定运行中。
1110 1
8套三级医院应用的管理系统源码,直接上项目,HIS、LIS、PACS
|
SQL 关系型数据库 MySQL
[Python]使用Python操作MySQL数据库(pymysql)
[Python]使用Python操作MySQL数据库(pymysql)
【问题解决】typora+picgo上传图片一直在uploading的解决方法
我们在typora+picgo搭建完图床后,我们需要上传图片,我们上传图片时,发现一直在uploading转圈圈,因此我去查询了解决方法,并且成功的解决问题了 问题情况如下图:
239 0
|
存储 编译器 对象存储
[Eigen中文文档] 包含Eigen对象的结构体
如果定义的结构体包含固定大小的可向量化 Eigen 类型成员,则必须确保对其调用 operator new 来分配正确的对齐缓冲区。如果仅使用足够新的编译器(例如,GCC>=7、clang>=5、MSVC>=19.12)以 [c++17] 模式编译,那么编译器会自动处理所有事情,可以跳过本节。 否则,必须重载它的 operator new 以便它生成正确对齐的指针(例如,Vector4d 和 AVX 的 32 字节对齐)。幸运的是,Eigen 为提供了一个宏 EIGEN_MAKE_ALIGNED_OPERATOR_NEW 来完成这项工作。
383 0