【学习挑战赛】经典算法之折半查找

简介: 【学习挑战赛】经典算法之折半查找

折半查找算法解析

一、什么是折半查找?

折半查找又称二分查找,它要求待查找的数据元素必须是按关键字大小有序排列的。给定已排好序的n个元素s1,…,sn,现要在这n个元素中找出一特定元素x。


首先较容易想到使用顺序查找方法,逐个比较s1,…,sn,直至找出元素x或搜索遍整个序列后确定x不在其中。

显然,该方法没有很好地利用n个元素已排好序这个条件。因此,在最坏情况下,顺序查找方法需要O(n)次比较。

二、折半算法思想

假定元素序列已经由小到大排好序,将有序序列分成规模大致相等的两部分,然后取中间元素与特定查找元素x进行比较:


如果x等于中间元素,则算法终止;

如果x小于中间元素,则在序列的左半部继续查找,即在序列的左半部重复分解和治理操作;

否则,在序列的右半部继续查找,即在序列的右半部重复分解和治理操作。

二分查找算法重复利用了元素间的次序关系。

三、构造折半查找实例

创建数组并随机赋值,定义low为数组左边界high为数组右边界(数组长度-1)middle为数组长度的一半。middle=(low+high)/2,即指示中间元素;我们需要通过代码来每次折半查找我们需要的元素值。


图示:(假设想要查找15)


第一次二分查找,找到25

021e6e0691f04162b785e0dea5875892.png

第二次二分查找,找到15

7c2d4e578aa543a99161230a3dbc6bd3.png

四、多种代码形式实现

非递归实现:


1.twoFind1()

int twoFind1(int A[], int len, int K)
{
  int low = 0, high = len - 1,middle;
  if (low > high) return -2;
  while (low <= high)//包含等于的情况
  {
    middle = (low + high) / 2;
    if (K == A[middle]) return middle;
    else if (K > A[middle]) low = middle + 1;
    else high = middle - 1;
  }
  return -1;
}

2.twoFind2()

int twoFind2(int A[], int len, int K)
{
  int low = 0, high = len - 1,middle;
  if (low > high) return -2;
  while (low < high)//不含等于的情况,并在最后做判断
  {
    middle = (low + high) / 2;
    if (K == A[middle]) return middle;
    else if (K > A[middle]) low = middle + 1;
    else high = middle - 1;
  }
  if (low == high && A[low] == K) return low;
  return -1;
}

递归实现:

int twoFind3(int A[], int k, int low, int high)
{
  int middle;
  if (low > high) return -1;//递归结束条件
  middle = (low + high) / 2;
  if (low==high && A[middle] == k) return middle;
  if (low < high) {
    if (A[middle] < k)      return  twoFind3(A, k, middle + 1, high);
    else  if(A[middle]==k)  return middle;
    else                    return  twoFind3(A, k, 0, middle - 1);
  }
  return -1;
}

建议大家用纸笔配合代码执行过程来分析每一步的运行情况,这样理解起来尤为快也不容易忘记。


五、时间复杂度分析

f5b076dfdb7d4f3b8ae5a27056807639.png


本文算法基础之折半查找结束,期待大家的支持~


目录
相关文章
|
8天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
4天前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
8天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
8天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!